72. Edit Distance

Dynamic Programming

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

        // Initialize
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }

        // Fill DP table
        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] = 1 + Math.min(
                        dp[i - 1][j],           // delete
                        Math.min(dp[i][j - 1],  // insert
                                 dp[i - 1][j - 1]) // replace
                    );
                }
            }
        }

        return dp[m][n];
    }
}

Remarks:

1. TC: $O(m\times n)$, SC: $O(m \times n)$.
2. DP idea: we record the minimum operations needed to convert the first $i$ characters in word1 to the first $j$ characters in word2 as dp[i][j].
3. Transform relationship:
   a. if the two chars match, then we don’t need any extra operation, i.e.
   $$
   dp[i][j] = dp[i-1][j-1]
   $$
   b. if they doesn’t match, we have 3 operations:
   (i) Insert a char, we add an char to word2[j-1],
   $$
   dp[i][j] = dp[i][j-1] + 1
   $$
   (ii) Delete a char, we remove an char of word1[i-1],
   $$
   dp[i][j] = dp[i-1][j] + 1
   $$
   (iii) Replace a char, we convert word1[i-1] to word2[j-1]
   $$
   dp[i][j] = dp[i-1][j-1] + 1
   $$
   We choose the minimum of all these three.
4. Initialization: $dp[0][j] = j$ (we add j chars to convert a empty string to first j chars), $dp[i][0] = i$.