0072. Edit Distance

https://leetcode.com/problems/edit-distance

Description

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

• Insert a character

• Delete a character

• Replace a character

Example 1:

**Input:** word1 = "horse", word2 = "ros"
**Output:** 3
**Explanation:** 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

**Input:** word1 = "intention", word2 = "execution"
**Output:** 5
**Explanation:** 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

Constraints:

• 0 <= word1.length, word2.length <= 500

• word1 and word2 consist of lowercase English letters.

ac

class Solution {
    public int minDistance(String word1, String word2) {
        // edge case
        if (word1 == null || word2 == null) return 0;

        int n1 = word1.length();
        int n2 = word2.length();
        int[][] dp = new int[n1+1][n2+1];

        // init
        for (int i = 0; i <= n1; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n2; j++) {
            dp[0][j] = j;
        }

        // func transformation
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <=n2; j++) {
                if (word1.charAt(i-1) == word2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
                }
            }
        }

        // res
        return dp[n1][n2];
    }
}
/*
DP

state: dp[i][j] minimun steps convert w1[0,i] to w[0,j]
func:
    (1)identical, if word1.charAt(i-1) == word2.charAt(j-1), dp[i][j] = dp[i-1][j-1]
    (2) 3 operations:
        1) insert: dp[i][j] = dp[i][j-1] + 1;
        2) delete: dp[i][j] = dp[i-1][j] + 1;
        3) replace: dp[i][j] = dp[i-1][j-1] + 1;
init: dp[0][j] = j; dp[i][0] = i;
res: dp[n1+1][n2+1]
*/

less space

class Solution {
    public int minDistance(String word1, String word2) {
        // edge cases
        if (word1 == null || word2 == null) return 0;

        int len1 = word1.length();
        int len2 = word2.length();
        int[] dp = new int[len1+1];
        for (int c = 1; c < dp.length; c++) dp[c] = dp[c-1] + 1; // init

        for (int r = 1; r <= len2; r++) {
            int leftRight = dp[0];
            for (int c = 0; c < dp.length; c++) {
                int old = dp[c];

                if (c == 0) {
                    dp[c]++;
                } else if (word1.charAt(c-1) == word2.charAt(r-1)) {
                    dp[c] = leftRight;
                } else {
                    dp[c] = Math.min(dp[c]+1, Math.min(dp[c-1]+1, leftRight+1));  // insert, delete, replace
                }

                leftRight = old;
            }
        }

        return dp[len1];
    }
}

/*
state: f[r][c] min convert word1.substring(0, c) to word2.substring(0, r);
func: 1) if word1.charAt(c-1) == word2.charAt(r-1), f[r][c] = f[r-1][c-1]
        2) 
            1) insert, f[r][c] = f[r-1][c] + 1
            2) delete, f[r][c] = f[r][c-1] + 1
            3) replace, f[r][c] = f[r-1][c-1]
*/