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

public class Solution {
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     * 最长公共子序列 ，没有说连续的，只要相等就可以记录下来。主要在寻找动态规划的公式
     * dp[i][j] dp[0][j] d[[i][0] 代表 s1 长度为0 和 s2 长度为0  i,j 代表长度i和长度j的公共子序列，下标为0..i-1,0..j-1
     */
    public String LCS (String s1, String s2) {
        // write code here
        if(s1 == null || s2 == null){
            return "-1";
        }
        //字符串 s1 中 0 .. i 和 s2中 0... j 中最大的子序列长度
        //先找到公式 dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])
        // 下标0 ..i -1  和 0...j -1 的最大公共子序列
        int[][] dp = new int[s1.length() + 1][s2.length() +1];
        int m = s1.length() +1;
        int n = s2.length() +1;
        for(int i = 0 ;i<m; i++){
            for(int j = 0 ;j< n;j++){
                if(i == 0|| j == 0){
                    dp[i][j] = 0;
                    continue;
                }
                if(s1.charAt(i-1) == s2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        int s1L = m-1 , s2L = n-1;
        StringBuilder sb = new StringBuilder();
        while(s1L != 0 && s2L != 0){
            if(s1.charAt(s1L - 1) == s2.charAt(s2L - 1)){
                sb.append(s1.charAt(s1L - 1));
                s1L --;
                s2L --;
            }else{
                if(dp[s1L - 1][s2L] > dp[s1L][s2L - 1]){
                    s1L --;
                }else{
                    s2L --;
                }
            }
            
        }
        if(sb.length() == 0){
            return "-1";
        }
        
        return sb.reverse().toString();
        
      
    }
}