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

import java.util.*;


public class Solution {
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    public void f1(String s1,String s2,int[][]dp){
        char []str1=s1.toCharArray();
        char []str2=s2.toCharArray();
        for(int i=1;i<dp.length;i++){
            for(int j=1;j<dp[i].length;j++){
                //dp[i][j]的值只可能来源于三个地方
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                if(str1[i]==str2[j]){
                    dp[i][j]=Math.max(dp[i][j],dp[i-1][j-1]+1);
                }
            }
        }
    }
    public String LCS (String s1, String s2) {
        // write code here
        if(s1.equals("")||s2.equals("")){//两个字符串有一个为空直接返回-1
            return "-1";
        }
        int n=s1.length();
        int m=s2.length();
        char []str1=s1.toCharArray();
        char []str2=s2.toCharArray();
        int [][]dp=new int[n][m];//dp[i][j]的含义为S1[0..i]和s2[0..j]的最长序列长度
        //初始化dp数组
        if(str1[0]==str2[0])
            dp[0][0]=1;
        //初始化dp第一行
        for(int j=1;j<dp[0].length;j++){
            dp[0][j]=Math.max(dp[0][j-1],str1[0]==str2[j]?1:0);
        }
        //初始化第一列
        for(int i=1;i<dp.length;i++){
            dp[i][0]=Math.max(dp[i-1][0],str1[i]==str2[0]?1:0);
        }
        f1(s1,s2,dp);
        char []res=new char[dp[n-1][m-1]];//开辟一个和最长序列一样长的结果数组
        int index=dp[n-1][m-1];
        if(index==0){
            return "-1";
        }
        n--;m--;
        while(index>0){
            if(m>0&&dp[n][m-1]==dp[n][m]){
                m--;
            }
            else if(n>0&&dp[n-1][m]==dp[n][m]){
                n--;
            }
            else{
                res[--index]=str1[n];
                n--;m--;
            }
        }
        return String.valueOf(res);
    }
}