最长公共子序列

先计算dp数组 初始化dp数组 dp数组递推公式

s1L s2L 两个指针分别指向s1,s2的末端 ，对比dp[i-1][j] dp[i][j-1],哪个较大就移动哪个的指针 如果dp[i-1][j] 较大 移动s1的指针s1L

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) {
        char[] s1Arr  = s1.toCharArray();
        char[] s2Arr  = s2.toCharArray();
        int len1 = s1Arr.length;
        int len2 = s2Arr.length;
        if (s1 == null || s2 == null || len1==0|| len2==0){
            return "-1";
        }
        int[][] dp = new int[len1+1][len2+1];
        int maxLen = 0;
        int s1End = 0;
        int s2End = 0;
        for (int i = 1; i < len1+1; i++) {
            char c1 = s1Arr[i-1];
            for (int j = 1; j < len2+1; j++) {
                char c2 = s2Arr[j-1];
                if (c1 == c2){
                    dp[i][j] = dp[i-1][j-1]+1;

                }else {
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
                if (dp[i][j]>maxLen){
                    maxLen = Math.max(maxLen,dp[i][j]);
                     s1End = i;
                     s2End = j;
                }
            }
        }
        //找出一个最长的公共子序列
        StringBuilder sb = new StringBuilder();
        int s1L = len1, s2L = len2;
        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();
    }
}