最长公共子序列「变题」

1143. 最长公共子序列

开头先来一个小插曲，关于「最长公共子序列」详细总结可见 最长公共子序列 (LCS)：「模版」&「输出」

public int longestCommonSubsequence(String text1, String text2) {
    int n1 = text1.length(), n2 = text2.length();
    int[][] dp = new int[n1 + 1][n2 + 1];
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            if (text1.charAt(i - 1) == text2.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]);
        }
    }
    return dp[n1][n2];
}

变题一：空间优化

public int longestCommonSubsequence(String text1, String text2) {
    int n1 = text1.length(), n2 = text2.length();
    int[] dp = new int[n2 + 1];
    for (int i = 1; i <= n1; i++) {
        int prevUp = 0;
        for (int j = 1; j <= n2; j++) {
            int t = prevUp;
            prevUp = dp[j];
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) dp[j] = t + 1;
            else dp[j] = Math.max(dp[j], dp[j - 1]);
        }
    }
    return dp[n2];
}

变题二：输出最长公共子序列

public int longestCommonSubsequence(String text1, String text2) {
    int n1 = text1.length(), n2 = text2.length();
    int[][] dp = new int[n1 + 1][n2 + 1];
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            if (text1.charAt(i - 1) == text2.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]);
        }
    }
    StringBuffer sb = new StringBuffer();
    int i = n1, j = n2;
    while (i > 0 && j > 0) {
        if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
            sb.append(text1.charAt(i - 1));
            i--; j--;
        } else if (dp[i - 1][j] < dp[i][j - 1]) {
            j--;
        } else i--;
    }
    System.out.println(sb.reverse().toString());
    return dp[n1][n2];
}