[LeetCode]72. Edit Distance

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:

  • Insert a character
  • Delete a character
  • Replace a character
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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')

Solution

Analysis

题目是说,给定两个字符串,string1, string2, 计算将string1变为string2的最少操作数. 对string1操作包括三种:插入/删除/替换.

最先想到的是使用递归方法. string1和string2对比,

  • string1为空, 返回string2的长度: 对string1进行插入操作, 所以操作数是string2的长度
  • string2为空, 返回string1的长度: 对string1进行删除操作, 所以操作数是string1的长度.
  • 一般情况下, 根据string1和string2的当前字符是否相等,可以细分为两种情况:
    • string1[0] == string2[0]: 对string1[1:]子串和string2[1:]子串递归调用
    • string1[0] != string2[0]: 分别计算,
      1. 当前操作是插入操作时,两个子串string1, string2[1:]的操作数
      2. 当前操作是删除操作时,两个子串string1[1:], string2的操作数
      3. 当前操作是替换操作时,两个子串string1[1:], string2[2:]的操作数
      4. 最终操作数是三者最小的数,再加1.
  • 返回结果.

但是, 递归法提交后,时间越界, 时间复杂度过高.

正确的方法是使用动态规划法. 这里的动态规划是二维的动态规划, 称为动态规划数组. 状态dp[i][j]:表示string1子串0-i, 变换成string2子串0-j的最少操作数[编辑距离] 状态转移方程, 根据递归方法的分析, 可以知道

dp[i][j], 根据string1[i] 和string[j]是否相等

string1[i] == string2[j]: dp[i][j] = dp[i-1][j-1] string1[i] != string2[j]: dp[i][j] = 1 + min(dp[i-1][j], min(dp[i][j-1], dp[i][j]))

但是,这里的二维动态规划矩阵多了一行和一列,作为辅助数组: 第一行和第一列, 分别表示当string1为空时,变为string2各子串的编辑距离; 当string2为空时,string1各个子串变为string2的编辑距离. 所以实际上,string1和string2的字符比较时的下标i,j和二维动态数组差一行, 差一列. 具体看代码.

Code

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int minDistance(string word1, string word2) {
if (word1 == word2) return 0;
int m = word1.size(), 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{
int insert_count = minDistance(word1, word2.substr(1));
int delete_count = minDistance(word1.substr(1), word2);
int replace_count = minDistance(word1.substr(1), word2.substr(1));

return 1 + min(insert_count, min(delete_count, replace_count));
}
}
};

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int minDistance(string word1, string word2) {
// 二维动态规划
int size1 = word1.size(), size2 = word2.size();
vector<vector<int>> dp(size1+1, vector(size2+1, 0));

for (int j=0; j<= size2; j++)// 辅助数组
dp[0][j] = j;
for (int j=0; j<= size1; j++)// 辅助数组
dp[j][0] = j;

for (int i=1; i<= size1; i++){
for (int j=1; j<= size2; j++){
if (word1[i-1] == word2[j-1])// 第一个字符开始
dp[i][j] = dp[i-1][j-1];
else
dp[i][j] = 1 + min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1]));
}
}
return dp[size1][size2];
}
};

References

https://www.cnblogs.com/grandyang/p/4344107.html

您的支持就是我更新的最大动力!谢谢!