题解 | #最长公共子序列(二)#

import java.util.*;


public class Solution {
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    String x="";String y="";
    public String ans(int i,int j,int[][]b ){//声明一个递归方法ans,根据当前两个字符串的索引以及对应的状态矩阵的值(1代表相等，2代表x向左移，3表示y向左移)判断如何操作，并返回最终的最长子串
        String res="";//声明res来装填相同的字符
        if(i==0||j==0){return res;}//当其中一个字符串左移完了后，停止递归
        else if(b[i][j]==1){res=res+ans(i-1,j-1,b)+y.charAt(j-1);}
        //状态值为1，则res加上上一级(两个字符串都左移)的ans值并加上当前索引时的字符
        else if(b[i][j]==2){res=res+ans(i-1,j,b);}
        //状态值为2，则res和x左移的ans值相等
        else if(b[i][j]==3){res=res+ans(i,j-1,b);}
        //状态值为3，则res和y左移时的ans值相等
        return res;
    }
    public String LCS (String s1, String s2) {
        // write code here
        x=s1;y=s2;
        int len1=s1.length();int len2=s2.length();
        if(len1==0||len2==0){return "-1";}
        int[][] dp=new int[len1+1][len2+1];
        //构造二维矩阵来记录s1到第i个字符,s2到第j个字符时的最大子串长度，因为需要记录s1或者s2第一个空字符用于后续往前递归，所以矩阵行列值必须比字符串长度多1
        int[][] b=new int[len1+1][len2+1];
        //构造二维状态矩阵来记录s1到第i个字符,s2到第j个字符时的状态值(1代表相等，2代表s1向左移，3表示s2向左移)
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
            //同时遍历s1和s2，对字符进行比较,如相同则长度dp+1,如不同则比较两种移动方式的dp并记录状态值
            if(x.charAt(i-1)==y.charAt(j-1)){dp[i][j]=dp[i-1][j-1]+1;b[i][j]=1;}
            else if(dp[i-1][j]>dp[i][j-1]){dp[i][j]=dp[i-1][j];b[i][j]=2;}
            else {dp[i][j]=dp[i][j-1];b[i][j]=3;}
            }
        }
        String res=ans(len1,len2,b);
        if(res.isEmpty()){return "-1";}
        return res;
    }
}