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

 public static String LCS (String s1, String s2) {
        String[][] dp = new String[s1.length()+1][s2.length()+1];
        for (int i1 = 0; i1 < dp.length; i1++) {
            for (int i2 = 0; i2 < dp[i1].length; i2++) {
                if(i1==0 || i2==0){
                    dp[i1][i2] = "";
                }else if(s1.charAt(i1-1)==s2.charAt(i2-1)){
                    dp[i1][i2] = dp[i1-1][i2-1] + s1.charAt(i1-1);
                }else if(s1.charAt(i1-1)!=s2.charAt(i2-1)){
                    String l1 = dp[i1-1][i2];
                    String l2 = dp[i1][i2-1];
                    dp[i1][i2] = l1.length()>l2.length()?l1:l2;
                }
            }
        }
        String result = dp[s1.length()][s2.length()];
        return result.length()>0?result:"-1";
 }