72. Edit Distance

DFS

class Solution {
    public int minDistance(String word1, String word2) {
        return dp(word1, word2, word1.length()-1, word2.length()-1);
    }
    private int dp(String word1, String word2, int i, int j) {
        if (i == -1) { // base case: if i is running out, means needs insert char, so cuurrent j len +1 operation(insert) (to convert to like j)
            return j+1;
        }
        if (j == -1) { // if j is running out, means needs delete char in i, so len i +1 operation(delete)
            return i+1;
        }
        if (word1.charAt(i) == word2.charAt(j)) {
            return dp(word1, word2, i-1, j-1); // same, skip, no need any operation
        } else {
            return min(
                dp(word1, word2, i-1, j)+1,   // delete in i
                dp(word1, word2, i, j-1)+1,   // insert in i
                dp(word1, word2, i-1, j-1)+1  // replace
            );
        }
    }
    private int min(int i, int j, int k) {
        return Math.min(Math.min(i, j), k);
    }
}

memo + DFS

class Solution {
    public int minDistance(String word1, String word2) {
        return dp(word1, word2, word1.length()-1, word2.length()-1, new Integer[word1.length()][word2.length()]);
    }
    private int dp(String word1, String word2, int i, int j, Integer[][] memo) {
        if (i == -1) { // base case: if i is running out, means needs insert char, so cuurrent j len +1 operation(insert) (to convert to like j)
            return j+1;
        }
        if (j == -1) { // if j is running out, means needs delete char in i, so len i +1 operation(delete)
            return i+1;
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        if (word1.charAt(i) == word2.charAt(j)) {
            return memo[i][j] = dp(word1, word2, i-1, j-1, memo); // same, skip, no need any operation
        } else {
            return memo[i][j] = min(
                dp(word1, word2, i-1, j, memo)+1,   // delete in i
                dp(word1, word2, i, j-1, memo)+1,   // insert in i
                dp(word1, word2, i-1, j-1, memo)+1  // replace
            );
        }
    }
    private int min(int i, int j, int k) {
        return Math.min(Math.min(i, j), k);
    }
}

DP

time: O(mn)

space: O(mn)

class Solution {
    public int minDistance(String word1, String word2) {
        /*
        if (word1[i-1] == word2[j-1]) 
            dp[i][j] = dp[i-1][j-1];
        else 
            dp[i][j] = Math.min(dp[i-1][j-1]+1, dp[i][j-1]+1, dp[i-1][j]+1);
        */
        int m = word1.length();
        int n = word2.length();
        int dp[][] = new int[m+1][n+1]; // dp[m][n] => so m+1, n+1
        
        // 當 j 都是空字串時, 代表i 要刪除掉 長度 i 的字串, 兩者才能長度一致
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        
        // 當 i 都是空字串時, 代表 i 要加入 長度 j 的字串, 兩者才能長度一致
        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] = Math.min(dp[i-1][j-1], Math.min(dp[i][j-1], dp[i-1][j])) + 1;
                }
            }
        }
        
        return dp[m][n];
    }
}

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m+1][n+1]; // include empty 
        
        word1 = "#" + word1;
        word2 = "#" + word2;
        
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i; // when j is empty, need delete i char
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j; // when i is empty, need insert j char
        }
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i) == word2.charAt(j)) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = min(
                        dp[i-1][j]+1,
                        dp[i][j-1]+1,
                        dp[i-1][j-1]+1
                    );
                }
            } 
        }
        return dp[m][n];
    }
    private int min(int i, int j, int k) {
        return Math.min(Math.min(i, j), k);
    }
}

/*
TC: O(mn)
SC: O(mn)

dp: the minimum number of operations required to convert word1[0:m] to word2[0:n]

if (word1[i] == word2[j]) {
// skip
    dp[i][j] = dp[i-1][j-1];
} else {
    min(
        dp[i-1][j]+1,  // delte char in i,   so + 1 operation
        dp[i][j-1]+1,      // insert char in i,  so + 1 operation
        dp[i-1][j-1]+1    // replace char in i, so + 1 operation
    )
}

*/

optimized to 1D space