72. 编辑距离

Posted on In , Views: Disqus:
LeetCode刷题系列。

描述

给定两个单词 word1word1 和 word2word2，计算出将 word1word1 转换成 word2word2 所使用的最少操作数 。

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

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

示例 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

解题思路

编辑距离问题就是给我们两个字符串word1和word2，只能用三种操作，让我们把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 n，m和n分别为 word1 和 word2 的长度。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]={dp[i−1][j−1]if word1[i−1]=word2[j−1]min⁡(dp[i−1][j−1],dp[i−1][j],dp[i][j−1])+1otherwisedp[i][j] = \begin{cases} dp[i-1][j-1] & \text{if } word1[i-1] = word2[j-1] \\ \min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1 & \text{otherwise} \end{cases}

具体代码见解法二。

代码

解法一：递归+记忆数组

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

参考