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

代码精简版

public static String LCS (String s1, String s2) {
        // write code here
        int n1 = s1.length(), n2 = s2.length();
        String[][] dp = new String[n1+1][n2+1];
        String res = "";
        for (int i=0;i<=n1;i++){
            for (int j=0;j<=n2;j++){
                // 所有的string都要初始化
                dp[i][j] = "";
                if (i == 0 || j == 0) continue;
                String c1 = s1.substring(i-1, i);
                String c2 = s2.substring(j-1, j);
                if (c1.equals(c2)){
                    dp[i][j] = dp[i-1][j-1] + c1;
                    if (dp[i][j].length() > res.length()){
                        res = dp[i][j];
                    }
                }else {
                    dp[i][j] = dp[i][j-1].length()>=dp[i-1][j].length() ? dp[i][j-1] : dp[i-1][j];
                }
            }
        }
        return res.equals("") ? "-1" : res;
    }