72. Edit Distance - cocoder39/coco39_LC GitHub Wiki

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        
        def helper(idx1, idx2):
            
            if idx1 == len(word1):
                return len(word2) - idx2
            
            if idx2 == len(word2):
                return len(word1) - idx1
            
            if memo[idx1][idx2] != -1:
                return memo[idx1][idx2]
            
            if word1[idx1] == word2[idx2]:
                return helper(idx1+1, idx2+1)
            
            insert = 1 + helper(idx1, idx2+1)
            delete = 1 + helper(idx1+1, idx2)
            replace = 1 + helper(idx1+1, idx2+1)
            
            memo[idx1][idx2] = min(insert, delete, replace)
            
            return memo[idx1][idx2]
        
        m, n = len(word1), len(word2)
        memo = [[-1] * n for _ in range(m)]
        return helper(0, 0)

int minDistance(string word1, string word2) {
        int m = word1.length();
        int n = word2.length();
        //dp[i][j] is distance from word1[0 ... i - 1] to word2[0 ... j - 1]
        vector<vector<int>> dp(m + 1, vector<int>(n + 1)); 
        
        dp[0][0] = 0;
        for (int i = 1; i <= m; i++) {
            dp[i][0] = dp[i - 1][0] + 1; //one more delete 
        }
        for (int j = 1; j <= n; j++) {
            dp[0][j] = dp[0][j - 1] + 1; //one more delete
        }
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else { //             replace             delete         insert
                    dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
                }
            }
        }
        return dp[m][n];
    }

int minDistance(string word1, string word2) {
        int m = word1.length();
        int n = word2.length();
        vector<vector<int>> dp(2, vector<int>(n + 1)); 

        dp[0][0] = 0;
        for (int j = 1; j <= n; j++) {
            dp[0][j] = dp[0][j - 1] + 1; //one more delete
        }

        int pre = 0, cur = 1;
        for (int i = 1; i <= m; i++) {
            dp[pre][0] = i - 1;
            dp[cur][0] = i;
            for (int j = 1; j <= n; j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[cur][j] = dp[pre][j - 1];
                }
                else { //             replace             delete         insert
                    dp[cur][j] = min(dp[pre][j - 1], min(dp[pre][j], dp[cur][j - 1])) + 1;
                }
            }
            swap(pre, cur);
        }
        return dp[pre][n];
    }