题解 | #最长公共子序列#

public String LCS (String s1, String s2) {
//        设置状态变量dp[i][j]：表示下标为[0,i-1]的s1和下标为[0,j-1]的s2的最长公共子序列的大小
        int[][] dp=new int[s1.length()+1][s2.length()+1];

        for (int i=1;i<s1.length()+1;i++){
            for (int j=1;j<s2.length()+1;j++){
                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 len1=s1.length();
        int len2=s2.length();

        StringBuilder sb = new StringBuilder();

        while (len1>0&&len2>0){
            //如果两个位置的字符相等，直接添加进sb中
            if (s1.charAt(len1-1)==s2.charAt(len2-1)){
                sb.append(s1.charAt(len1-1));
                len1--;
                len2--;
            }else {//如果不相等，则要根据dp[][]来判断应该向哪个方向移动
                if (dp[len1][len2-1]>dp[len1-1][len2]){//说明len2方向的有更多相同的字符，所以len2--
//                    说明dp[len1][len2]==dp[len1][len2-1],
                    len2--;
                }else {
                    len1--;
                }
            }
        }


        if (sb.length() == 0) return "-1";
        return sb.reverse().toString();
    }