72. 编辑距离

描述

给定两个单词 $word1$ 和 $word2$,计算出将 $word1$ 转换成 $word2$ 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

示例 1:

1
2
3
4
5
6
输入: word1 = "horse", word2 = "ros"
输出: 3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2:

1
2
3
4
5
6
7
8
输入: word1 = "intention", word2 = "execution"
输出: 5
解释:
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

来源:力扣(LeetCode)
链接:72. edit distance

解题思路

编辑距离问题就是给我们两个字符串word1word2,只能用三种操作,让我们把word1变成word2,求最少的操作数。需要明确的是,不管是把word1变成word2,还是反过来,结果都是一样的。

我们用i,j分别指针表示两个字符串中字符的位置,对于当前比较的两个字符 word1[i]word2[j],若二者相同,一切好说,直接跳到下一个位置,这其实也是一种处理的方式。若不相同,有三种处理方法,首先是直接插入一个word2[j],那么word2[j] 位置的字符就跳过了,接着比较word1[i]word2[j+1] 即可。第二个种方法是删除,即将word1[i] 字符直接删掉,接着比较word1[i+1]word2[j] 即可。第三种则是将word1[i] 修改为 word2[j],接着比较 word1[i+1]word[j+1] 即可。

这样可以写出递归的代码如下:

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
27
28
29
30
int min(int a, int b)
{
if (a > b) return b;
else return a;
}

int abs( int num )
{
if (num > 0) return num;
else return -num;
}

int minDistance(char* word1, char* word2)
{
if(strlen(word1) == 0 || strlen(word2) == 0)
{
return abs((int)strlen(word1) - (int)strlen(word2));
}

if(word1[0] == word2[0])
{
return minDistance(word1 + 1, word2 + 1);
}

int insertCnt = minDistance(word1, word2 + 1) + 1;
int deleteCnt = minDistance(word1 + 1, word2) + 1;
int replaceCnt = minDistance(word1 + 1, word2 + 1) + 1;

return min(min(insertCnt,deleteCnt),replaceCnt);
}

但是很可惜,这个代码会超时,所以必须要优化时间复杂度,需要去掉大量的重复计算,根据之前的套路,可以采用记忆数组memo来保存计算过的状态,可以考虑声明一个全局变量,并将其值都初始化为-1,具体解法见解法一。

根据以往的经验,对于字符串相关的题目且求极值的问题,十有八九都是用动态规划Dynamic Programming 来解,这道题也不例外。其实解法一的递归加记忆数组的方法也可以看作是DP的递归写法。这里需要维护一个二维的数组dp,其大小为m \times nmn分别为word1word2 的长度。dp[i][j] 表示从word1的前i个字符转换到word2 的前j个字符所需要的步骤。先给这个二维数组dp 的第一行第一列赋值,这个很简单,因为第一行和第一列对应的总有一个字符串是空串,于是转换步骤完全是另一个字符串的长度。跟以往的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

通过观察可以发现,当 word1[i] == word2[j] 时,dp[i][j] = dp[i - 1][j - 1],其他情况时,dp[i][j] 是其左,左上,上的三个值中的最小值加1,其实这里的左,上,和左上,分别对应的增加,删除,修改操作,具体可以参见解法一种的讲解部分,那么可以得到状态转移方程为:

$$
dp[i][j]=\left\{
\begin{array}{rcl}
dp[i-1][j-1] & & if \,\, word1[i-1] == word2[j - 1]\\
min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1 & & else
\end{array} \right.
$$

具体代码见解法二。

代码

解法一:递归+记忆数组

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#define MAXNUM 10000

int min(int a, int b)
{
if (a > b) return b;
else return a;
}

//声明memo为全局变量
int** memo = NULL;

int helper(char *word1, char *word2, int len1, int len2)
{
int target1 = strlen(word1);
int target2 = strlen(word2);
int minmum = MAXNUM;

if(len1 == 0 && len2 == 0)
{
return 0;
}

if(len1 == 0 && len2 > 0)
{
return helper(word1, word2, len1, len2 - 1) + 1;
}

if(len1 > 0 && len2 == 0)
{
return helper(word1, word2, len1 - 1, len2) + 1;
}

if(memo[len1][len2] > 0) return memo[len1][len2];

if(word1[target1 - len1] == word2[target2 - len2])
{
minmum = helper(word1, word2, len1 - 1, len2 - 1);
}
else
{
minmum = min(minmum, helper(word1, word2, len1, len2 - 1) + 1); //insert
minmum = min(minmum, helper(word1, word2, len1 - 1, len2 - 1) + 1); //replace
minmum = min(minmum, helper(word1, word2, len1 - 1, len2) + 1); //delete
}

return memo[len1][len2] = minmum;

}

int minDistance(char * word1, char * word2){

memo = (int **)malloc((strlen(word1) + 1) * sizeof(int *));

for (int i = 0; i < strlen(word1) + 1; i++)
{
memo[i] = malloc((strlen(word2) + 1) * sizeof(int));
}

for (int i = 0; i < strlen(word1) + 1; i++) {
for (int j = 0; j < strlen(word2) + 1; j++) {
memo[i][j] = -1;
}
}

return helper(word1, word2, strlen(word1), strlen(word2));

}

解法二:动态规划

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
int min(int a, int b)
{
if (a > b) return b;
else return a;
}

int minDistance(char * word1, char * word2)
{
int len1 = strlen(word1);
int len2 = strlen(word2);

int **dp = (int *)malloc(sizeof(int*) * (len1 + 1));
for (int i = 0; i <= len1; i++)
{
dp[i] = (int *)malloc(sizeof(int) * (len2 + 1));
dp[i][0] = i;
}

for (int j = 0; j <= len2; j++)
{
dp[0][j] = j;
}

if (len1 == 0)
{
return len2;
}

if (len2 == 0)
{
return len1;
}

for (int i = 1; i <= len1; i++)
{
for (int j = 1; j <= len2; j++)
{
if (word1[i - 1] == word2[j - 1])
{
dp[i][j] = dp[i - 1][j - 1];
}
else
{
dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
}
}
}

return dp[len1][len2];
}

参考