Leetcode72. 编辑距离

题目描述

给你两个单词 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')

提示：

  • 0 <= word1.length, word2.length <= 500
  • word1 和 word2 由小写英文字母组成

解题思路

涉及两个字符串之间的最大最小问题第一反应就是能不能使用动态规划，但是怎么定义状态，以及如何求出状态转移方程比较困难。

先研究一下题目。我们对一个单词的操作可以有三种，分别为：

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

那么两个单词A和B加起来就有就有六种方式。但是这六种方式有等价的操作：

  • 对单词A 删除一个字符和对单词 B 插入一个字符是等价的；

  • 对单词B 删除一个字符和对单词A 插入一个字符是等价的；

  • 对单词 A 替换一个字符和对单词 B 替换一个字符是等价的。

也就是说只剩下了三种不同的操作：

  • 在单词 A 中插入一个字符；
  • 在单词 B 中插入一个字符；
  • 修改单词 A 的一个字符。

现在我们研究一下如何用动态规划解决这个问题。如果我们定义dp[i][j]dp[i][j]为word1中前i个字符变换到word2中前j个字符所需要的最短操作次数，(i,j)(i,j)表示word1中前i个字符经过dp[i][j]dp[i][j]次最少操作变换到word2中前j个字符后的一个状态。那么(i,j)(i,j)状态是由(i−1,j),(i,j−1),(i−1,j−1)(i-1,j),(i,j-1),(i-1,j-1)变化而来的，也就是说dp[i][j]dp[i][j]的值跟dp[i−1][j],dp[i][j−1],dp[i−1][j−1]dp[i-1][j],dp[i][j-1],dp[i-1][j-1]有关系了。

  • 如果(i,j)(i,j)由(i−1,j)(i-1,j)变化而来，那么只需在(i−1,j)(i-1,j)的基础上在单词 A 中插入一个字符，也就是说，存在等式：

dp[i][j]=dp[i−1][j]+1dp[i][j]=dp[i-1][j]+1

  • 如果(i,j)(i,j)由(i,j−1)(i,j-1)变化而来，那么只需在(i,j−1)(i,j-1)的基础上在单词 B 中插入一个字符，也就是说，存在等式：

dp[i][j]=dp[i][j−1]+1dp[i][j]=dp[i][j-1]+1

  • 如果(i,j)(i,j)由(i−1,j−1)(i-1,j-1)变化而来，还需要考虑word1[i-1](word1的第i个字符)和word2[j-1](word2的第j个字符的值相等，则不需要任何操作；否则，修改单词 A 的一个字符。也就是存在以下公式：

dp[i][j]=dp[i−1][j−1]+1，ifword1[i−1]=word2[j−1]dp[i][j]=dp[i−1][j−1],ifword[i−1]≠word2[j−1]dp[i][j]=dp[i-1][j-1]+1，\quad if \quad word1[i-1]=word2[j-1]\\\\ dp[i][j]=dp[i-1][j-1], \quad if \quad word[i-1]\neq word2[j-1]

然后我们考虑一些特殊情况。

  • 当A和B都是空字符串的时候，也就是(0,0)(0,0)状态下，dp[0][0]=0dp[0][0]=0；
  • 当A或者B有且只有一个为空的时候，只需要逐个删除非空字符串的字符就可。也就是说：

ifA字符串为空字符串,dp[0][j]=j;ifB字符串为空字符串,dp[i][0]=i;if \quad A字符串为空字符串, \quad dp[0][j]=j;\\\\ if \quad B字符串为空字符串, \quad dp[i][0]=i;

我们总结一下不难得到以下的动态规划条件：

\begin{eqnarray} && if \quad i=0 \quad 并且 \quad j=0,\quad dp[0][0]=0;\\\\ && if \quad i=0 \quad 并且 \quad j\neq 0,\quad dp[0][j]=j;\\\\ && if \quad i\neq 0 \quad 并且 \quad j=0,\quad dp[i][0]=i;\\\\ && if \quad i\neq 0 \quad 并且 \quad j\neq 0, \\\\ && dp[i][j]=min(dp[i][j-1]+1,dp[i-1][j]+1,dp[i-1][j-1]+1) ,\quad && if \quad word1[i-1] \neq word2[j-1];\\\\ && dp[i][j]=min(dp[i][j-1]+1,dp[i-1][j]+1,dp[i-1][j-1]), \quad && if \quad word1[i-1] = word2[j-1]; \end{eqnarray}

据此可以写出对应代码，具体细节见示例代码：

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
int minDistance(string word1, string word2)
{
    int m=word1.size();
    int n=word2.size();
    vector<vector<int>>dp(m+1,vector<int>(n+1,0));
    for(int i=1;i<m+1;++i)
    {
        dp[i][0]=i;
    }
    for(int i=1;i<n+1;++i)
    {
        dp[0][i]=i;
    }
    for(int i=1;i<=m;++i)
    {
        for(int j=1;j<=n;++j)
        {
            if(word1[i-1]!=word2[j-1])
            {
                dp[i][j]=min(dp[i][j-1]+1,min(dp[i-1][j]+1,dp[i-1][j-1]+1));
            }
            else{
                dp[i][j]=min(dp[i][j-1]+1,min(dp[i-1][j]+1,dp[i-1][j-1]));
            }
        }
    }
    return dp[m][n];
}

时间复杂度为：O(m×n)O(m \times n)，mm和nn分别为word1和word2的长度；

空间复杂度为：O(m×n)O(m \times n)，mm和nn分别为word1和word2的长度。