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

思路:
1.题目给出目前给出的数据，仅仅会存在一个最长的公共子序列
2.我们利用dp[i][j] 记录 字符串s1的0到i-1位置与字符串s2的0到j-1位置的最长公共子序列长度
3.如果s1.charAt(i-1) == s2.charAt(j-1) ,那么dp[i][j] = dp[i-1][j-1] + 1, 不相等则，dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]
4.我们从字符串后面遍历到前面，如果相等，我们就记录下来，不相等，就看下当前位置[i-1][j]与[i][j-1]的最大公共子序列长度，选择往大的方向偏移，确定最大子序列来自的方向是哪。例如dp[i-1][j]大，那么说明最长公共子序列转变成了 s1[0,i-1]与s2[0][j]的最大公共子序列

import java.util.*;


public class Solution {
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    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][s2L - 1] > dp[s1L -1][s2L]){
                    s2L --;
                }else{
                    s1L --;
                }
            }
        }
        if(sb.length() == 0){
            return "-1";
        }
        return sb.reverse().toString();
      
    }
}