Advanced Longest Common Subsequence

Longest Common Subsequence (LCS: LeetCode 1143)

dp[i][j] = length of LCS between text1[0..i-1] and text2[0..j-1].

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];
}

Edit Distance (LeetCode 72)

The minimum number of operations (insert, delete, replace) to convert word1 to word2.

dp[i][j] = min operations to transform prefix of length $i$ to prefix of length $j$.

public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    
    // Boundary: transform string to am empty string
    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]; // Chars match, no action needed
            else
                dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], // Replace
                               Math.min(dp[i - 1][j],    // Delete
                                        dp[i][j - 1]));  // Insert
        }
    }
    return dp[m][n];
}

Delete Operation for Two Strings (LeetCode 583)

Find the minimum number of character deletions such that both strings are equal.

Reduction: The surviving string will be the LCS. Minimum deletions = len(s1) + len(s2) - 2 * LCS(s1, s2).

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

Shortest Common Supersequence (LeetCode 1092)

Find the shortest string that contains both s1 and s2 as subsequences. Length = len(s1) + len(s2) - LCS(s1, s2).

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]);
    
    // Backtrack the DP table to construct the resulting string
    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();
}

At a Glance Comparison Table