583. Delete Operation for Two Strings

https://leetcode.com/problems/delete-operation-for-two-strings/

Python

Bottom-up DP with LCS

See 1143. Longest Common Subsequence for detail

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        lcs = self.longestCommonSubsequence(word1, word2)
        return len(word1)-lcs + len(word2)-lcs
    
    
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [[0]*(len(text2)+1) for _ in range(len(text1)+1)]

        for col in range(len(text2)-1, -1, -1):
            for row in range(len(text1)-1, -1, -1):
                if text2[col] == text1[row]:
                    dp[row][col] = 1 + dp[row+1][col+1]
                else:
                    dp[row][col] = max(dp[row+1][col], dp[row][col+1])
        return dp[0][0]

JS

var minDistance = function(word1, word2) {
    // if (word1 === word2) return 0;
    const dp = [...new Array(word1.length + 1)].map(() => new Array(word2.length + 1).fill(0));
    
    for (let i = 0; i <= word1.length; i++) {
        for (let j = 0; j <= word2.length; j++) {
            if (i === 0 || j === 0 ) dp[i][j] = 0;
            else {
                if (word1[i - 1] === word2[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]);
                }
            }
        }
    }
    // console.log(dp)
    return (word1.length + word2.length) - 2 * dp[word1.length][word2.length];
};

/***
 *   " s e a    " a
 * " 0 0 0 0  " 0 0
 * e 0 0 1 1  b 0 0
 * a 0 0 1 2
 * t 0 0 1 2
 */