Leetcode(72) Edit Distance

发表于 | 分类于

Description

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')

解法

最开始的时候看到这道题是懵逼的，深呼吸，来分析以下具体情况。

假设从左往右进行字符串修改，如果A[i] == b[j]，此时此刻，因为是从左向右修改的，那么，i之前的字符串与j之间的字符串已经匹配了，又因为i和j对应的字符相等，那么需要修改的次数就是i-1修改为j-1的次数。

如果A[i]!=B[j]，此时题目中给出了三种修改方案，一种是直接删除字符，那么此时的修改次数就是修改i-1为j的次数+1（对应递归中i指针向后移一位），一种是插入新字符，那么此时的修改次数就是修改i为j-1的次数+1（对应递归中j指针向后移一位），一种是直接替换，那么此时的修改次数就是修改i-1为j-1的次数+1（对应递归中i,j指针往后移一位）。

维护一个二维的数组dp，其中dp(i,j)表示从word1的前i个字符转换到word2的前j个字符所需要的步骤。那我们可以先给这个二维数组dp的第一行第一列赋值，这个很简单，因为第一行和第一列对应的总有一个字符串是空串，于是转换步骤完全是另一个字符串的长度。我们可以举个例子来看，比如word1是“bbc”，word2是”abcd“，那么我们可以得到dp数组如下：

1
2
3
4
5
  Ø a b c d
Ø 0 1 2 3 4
b 1 1 1 2 3
b 2 2 1 2 3
c 3 3 2 1 2

有递推公式：

1
2
3
4
if word1[i - 1] == word2[j - 1]
dp[i][j] = dp[i - 1][j - 1] 
else
dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1

具体代码如下：

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 i = 0; i < word1.length() + 1; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j < word2.length() + 1; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i < word1.length() + 1; i++) {
            for (int j = 1; j < word2.length() + 1; 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;
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }
}

一般动态规划的题可以用递归来解，以下网上给出的递归方法，可以帮助我们理解dp公式。当然肯定是超时的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int minDistance(string word1, string word2) {
        if(word1 == word2) return 0;
         
        int m = word1.size();
        int n = word2.size();
         
        if(word1 == "")
        {
            return n;
        }
         
        if(word2 == "")
        {
            return m;
        }
         
        if(word1[0] == word2[0])
        {
            return minDistance(word1.substr(1), word2.substr(1));
        }
        else
        {
            return min(1 + minDistance(word1, word2.substr(1)), min(1 + minDistance(word1.substr(1), word2), 1 + minDistance(word1.substr(1), word2.substr(1))));
        }
 
    }