[LeetCode] 72. Edit Distance

Posted on | In

Problem

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

  1. Insert a character
  2. Delete a character
  3. Replace a character

Example 1:

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

Example 2:

1
2
3
4
5
6
7
8
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')

Explanation

  1. We can use dynamic programming to solve this problem. For example, word1 = “12b45”, word2 = “abcde”. We can draw a dynamic table like below.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
         word2
          empty   a    b    c    d    e
 word1 +----------------------------------+
       |
 empty |    0     1    2    3    4    5
       |
    1  |    1     1    2    3
       |
    2  |    2     2    2    3
       |
    b  |    3     3    2    3
       |
    4  |    4     4    3    3
       |
    5  |    5
       +

  2. State is dp[r][c], which represents the minimum operation to convert word1[0, r-1] to word2[0, c-1].

  3. Init is when word1 is empty (top row), if word2 is also empty, then there are 0 operation to convert word1 to word2; if word2 has length 1, then there are 1 insert operation to convert word1 to word2; if word2 has length 2, then there are 2 insert operations to convert word1 to word2; if word3 has length 3, then we need 3 insert operations, etc.

  4. When word2 is empty (left most column), if word1 is also empty, then there are we need 0 operation; if word1 has length 1, then we need 1 remove operation; if word1 has length 2, then we need 2 remove operation, etc.

  5. Dynamic function is if the last character of both words are the same, for example, word1 = “12b”, word2 = “ab”, then the number of operations we need is the same as comparing word1 = “12” and word2 = “a”. In other words, if the last characters of both words are the same, then dp[r][c] = dp[r-1][c-1].

  6. If the last character of both words are not the same, for example, word1 = “12b4”, word2 = “abc”, then we need to consider three cases:

    1. Delete “4” from word1, then compare word1 = “12b” and word2 = “abc”. In other word, dp[r][c] = 1 + dp[r-1][c].

    2. Replace “4” with “c”, then compare word1 = “12b” and word2 = “ab”. In other word, dp[r][c] = 1 + dp[r-1][c-1].

    3. Insert “c” at the end of word1, then compare word1 = “12b4” and word2 = “ab”. In other word, dp[r][c] = 1 + dp[r][c-1].

  7. If the last character of both words are not the same, we should take the minimum among these 3 operations as the result of dp[r][c].

  8. Dynamic result is dp[len(word1)][len(word2)] which is at the bottom right.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];

        for (int r = 0; r <= word1.length(); r++) {
            for (int c = 0; c <= word2.length(); c++) {
                if (r == 0) {
                    dp[r][c] = c;
                } else if (c == 0) {
                    dp[r][c] = r;
                } else if (word1.charAt(r-1) == word2.charAt(c-1)) {
                    dp[r][c] = dp[r-1][c-1];
                } else {
                    dp[r][c] = 1 + Math.min(dp[r-1][c-1], Math.min(dp[r-1][c], dp[r][c-1]));
                }
            }
        }

        return dp[word1.length()][word2.length()];
    }
}