LeetCode 72. 编辑距离 【c++/java详细题解】

目录

1、题目

给你两个单词

word1

和

word2

， 请返回将

word1

转换成

word2

所使用的最少操作数 。

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

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

示例 1：

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

示例 2：

输入：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 由小写英文字母组成

2、思路

(动态规划)

    O
   
   
    (
   
   
    n
   
   
    ∗
   
   
    m
   
   
    )
   
  
  
   O(n * m)
  
 
O(n∗m)

给你两个单词

word1

和

word2

，我们可以对一个单词进行插入一个字符，删除一个字符，替换一个字符三种操作，请你计算出将

word1

转换成

word2

所使用的最少操作数 。

样例：

如样例所示，

word1 = "horse"

,

word2 = "ros"

，我们将

word1

转换成

word2

所使用的最少操作数为

3

，下面来讲解动态规划的做法。

对于动态规划的题目来说，我们一般要考虑两个问题，分别是状态表示和状态计算。状态表示往往和题目的问题相关，因此我们可以定义如下状态表示。

状态表示：

f[i][j]

表示将

word1

的前

i

个字符变成

word2

的前

j

个字符所需要进行的最少操作次数。假设

word1

长度为

n

，

word2

长度为

m

，那么

f[n][m]

就表示将

word1

的前

n

个字符变成

word2

的前

m

个字符所需要进行的最少操作次数，即为答案。

有了状态表示以后，我们去进行状态计算，推导状态计算方程。

状态计算：

如何计算

f[i][j]

？考虑

word1

的第

i

个字符与

word2

的第

j

个字符，分为两种情况：

• 1、word1[i] == word2[j]，则f[i][j] == f[i - 1][j - 1];
• 2、word1[i] != word2[j]，我们有三种选择，替换、删除、插入： - 替换： 替换word1的第i个字符或者替换word2的第j个字符，则f[i][j] == f[i - 1][j - 1] + 1；- 删除： 删除word1的第i个字符或者删除word2的第j个字符，则f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;- 插入: 在 word2[j] 后面添加 word1[i]或者在word1[i]后添加word2[j]，则f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;

我们去解释一下上述状态计算：

当

word1[i] == word2[j]

时，当前两个字符相同，我们不需要做任何操作，此时

f[i][j]

就可以从

f[i - 1][j - 1]

的状态转移过来，换句话说，此时

f[i][j]

的状态取决于

f[i - 1][j - 1]

。

当

word1[i] != word2[j]

时，此时我们可以进行的操作有三种：

• 替换： 替换word1的第i个字符或者替换word2的第j个字符，当前位置的字符不匹配，进行替换操作后两者变得相同。
  
  所以

  f[i][j] == f[i - 1][j - 1] + 1
  

  。

• 删除： 删除word1的第i个字符或者删除word2的第j个字符。如果当前word1[0 ~ i-1] 与word2[0 ~ j]匹配，我们删除多余的word1[i]，或者word1[0 ~ i]与word2[0 ~ j-1]匹配，我们删除多余的word[j]。 两种情况的状态分别为f[i - 1][j]和f[i][j - 1]，因为题目要求最少操作数，故二者之间我们取一个最小值，所以f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1。

• 插入: 在 word2[j] 后面添加 word1[i]或者在word1[i]后添加word2[j]。如果当前word1[0 ~ i-1] 与word2[0 ~ j]匹配或者word1[0 ~ i]与word2[0 ~ j-1]匹配，除了考虑删除多余的字符操作以外，我们还可以执行添加操作，因此添加和删除的状态计算其实是一样的。所以f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1。

考虑完状态计算和状态转移以后，接下来我们去进行状态初始化。

3、初始化

for(int i =0; i <= n; i++)  f[i][0]= i;//将长度为i的word1变成长度为0的word2需要进行最少i次删除操作for(int i =0; i <= m; i++)  f[0][i]= i;//将长度为i的word2变成长度为0的word1需要进行最少i次删除操作

实现细节：

其实我们可以注意到，

word[]

数组下标如果从

1

开始的话，第

i

个字符就是

word[i]

，而不是下标从

0

开始的

word[i - 1]

，这样的

word[]

数组与我们的状态表示会更加相对应。因此，为了代码的可读性更高，我们给

word1[]

数组和

word2[]

数组的开头都去添加一个空格，然后在状态计算时，下标从

1

开始。

时间复杂度分析： 状态数为

    O
   
   
    (
   
   
    n
   
   
    ∗
   
   
    m
   
   
    )
   
  
  
   O(n * m)
  
 
O(n∗m)，状态计算为

 
  
   
    O
   
   
    (
   
   
    1
   
   
    )
   
  
  
   O(1)
  
 
O(1)，因此总的时间复杂度为

 
  
   
    O
   
   
    (
   
   
    n
   
   
    ∗
   
   
    m
   
   
    )
   
  
  
   O(n * m)
  
 
O(n∗m)。

4、c++代码

class Solution {
public:intminDistance(string word1, string word2){int n = word1.size(), m = word2.size();
        word1 =' '+ word1;//添加空格
        word2 =' '+ word2;
        vector<vector<int>>f(n +1, vector<int>(m +1));for(int i =0; i <= n; i++)  f[i][0]= i;//i次删除for(int i =0; i <= m; i++)  f[0][i]= i;//i次删除 word1 -> word2for(int i =1; i <= n; i++)for(int j =1; j <= m; j++){
                f[i][j]=min(f[i -1][j], f[i][j -1])+1;//添加或者删除if(word1[i]== word2[j]) f[i][j]=min(f[i][j], f[i -1][j -1]);else f[i][j]=min(f[i][j], f[i -1][j -1]+1);//替换}return f[n][m];}};

5、Java代码

classSolution{publicintminDistance(String word1,String word2){int n = word1.length(), m = word2.length();
        word1 =' '+ word1;//添加空格
        word2 =' '+ word2;int[][] f =newint[n +10][m +10];for(int i =0;i <= n;i++) f[i][0]= i;//i次删除for(int i =0;i <= m;i++) f[0][i]= i;//i次删除 word1 -> word2for(int i =1;i <= n;i++)for(int j =1;j <= m;j++){  
                f[i][j]=Math.min(f[i -1][j]+1, f[i][j -1]+1);//添加或者删除if(word1.charAt(i)== word2.charAt(j)) f[i][j]=Math.min(f[i][j], f[i -1][j -1]);else f[i][j]=Math.min(f[i][j], f[i -1][j -1]+1);//替换}return f[n][m];}}

原题链接： 72. 编辑距离