最长公共子序列进阶

最长公共子序列（LeetCode 1143）

dp[i][j] = text1[0..i-1] 与 text2[0..j-1] 的 LCS 长度：

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

编辑距离（LeetCode 72）

将 word1 变成 word2 的最小操作数（插入、删除、替换）：

dp[i][j] = word1[0..i-1] 变成 word2[0..j-1] 的最小步骤：

public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m+1][n+1];
    // 边界：将任意字符串变为空字符串
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i-1) == word2.charAt(j-1))
                dp[i][j] = dp[i-1][j-1]; // 字符相同，无需操作
            else
                dp[i][j] = 1 + Math.min(dp[i-1][j-1],   // 替换
                                Math.min(dp[i-1][j],      // 删除 word1[i-1]
                                         dp[i][j-1]));    // 插入（等价删除 word2[j-1]）
        }
    }
    return dp[m][n];
}

两个字符串的删除操作（LeetCode 583）

只能删除字符，使两字符串相等，求最少删除总步数：

等价于 m + n - 2 * LCS(s1, s2)：

public int minDistance(String word1, String word2) {
    int lcs = longestCommonSubsequence(word1, word2);
    return word1.length() + word2.length() - 2 * lcs;
}

最短公共超序列（LeetCode 1092）

求包含 s1 和 s2 作为子序列的最短字符串，长度 = m + n - LCS：

public String shortestCommonSupersequence(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m+1][n+1];
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = s1.charAt(i-1) == s2.charAt(j-1)
                ? dp[i-1][j-1] + 1 : Math.max(dp[i-1][j], dp[i][j-1]);
    // 回溯构建结果
    StringBuilder sb = new StringBuilder();
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (s1.charAt(i-1) == s2.charAt(j-1)) { sb.append(s1.charAt(i-1)); i--; j--; }
        else if (dp[i-1][j] > dp[i][j-1]) sb.append(s1.charAt(--i));
        else sb.append(s2.charAt(--j));
    }
    while (i > 0) sb.append(s1.charAt(--i));
    while (j > 0) sb.append(s2.charAt(--j));
    return sb.reverse().toString();
}

总结