72.编辑距离

发表于： 2023-07-01 分类于： leetcode

字数： 1767 阅读：≈ 4分钟

😄72.编辑距离

给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。

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

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

思路

基本思想

错误代码

首先想到的就是word1要转换成word2，那么相同的部分肯定不用理会，只有不相等的部分才需要进行增删改，那么就可以先求出其最长公共子序列的长度，剩下的元素就需要变动

在变动时，就看谁剩下的元素更多，那么就将这些元素全部变动，最终word1和word2相等，核心就是在求最长公共子序列上，但是发现这样只能通过一部分示例：

问题在"intention，execution"这两个字符串上，在元素e的匹配上，ention中间有个多余的n

ecution中间有两个多余的cu，程序判断的逻辑会造成错误，因为程序判断的逻辑为：

1
max(word1.size()-res,word2.size()-res);

res就是最长公共子序列，导致最后返回4，其实正确结果为5，错误代码为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>>dp(word1.size()+1,
                            vector<int>(word2.size()+1,0));
        int res=0;
        for(int i=0;i<word1.size();++i){
            for(int j=0;j<word2.size();++j){
                if(word1[i]==word2[j]){
                    dp[i+1][j+1]=dp[i][j]+1;
                }else{
                    dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
                }
                res=max(res,dp[i+1][j+1]);
            }
        }
        return max(word1.size()-res,word2.size()-res);
    }
};

按照思路分析，无非就是一下几个操作：

dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。

两个元素匹配，什么操作也不用做，例子为：word1(ab)，word2(ab)
也就是word1[i]==word2[j]
对应的公式为： $$ dp[i+1][j+1]=dp[i][j] $$
两个元素不匹配
也就是word1[i]!=word2[j]
- word1元素删除一个，例子为：word1(abc)，word2(ab)
  代表ab是匹配的，对应的公式为： $$ dp[i+1][j+1]=dp[i][j+1]+1 $$
- word1元素增加一个，例子为：word1(ab)，word2(abc)
  代表ab是匹配的，对应的公式为： $$ dp[i+1][j+1]=dp[i+1][j]+1 $$
  word1增加一个与word2删除一个操作数是一样的
- word1元素替换一个，例子为：word1(abc)，word2(abd)
  代表ab是匹配的，对应的公式为： $$ dp[i+1][j+1]=dp[i][j]+1 $$
  word1替换一个与word1和word2同时删除一个操作数是一样的

上面三种操作选取最小的操作数作为最终的结果即可

知道以上几种操作，剩下的事情就是确定dp数组的含义，本题中，dp[i][j]代表以第i个元素和第j个元素结尾最多需要经过多少步操作可以使两个字符串相同

dp[0][j]代表word1没有元素，word2有j个元素，此时word1需要经过j次增加才能与word2一致

也就是dp[0][j+1]=j+1

dp[i][0]代表word1有i个元素，word2没有元素，此时word1需要经过i次删除才能与word2一致

也就是dp[i+1][0]=i+1

知道这些之后就是更新dp数组了

执行流程

初始化dp数组，第一行第一列单独初始化，注意下标从0开始，所以初始化需要+1
按照公式更新dp数组
返回结果

代码

根据以上分析，得出以下代码：

 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
class Solution {
public:
    //dp[i+1][j+1]代表[0,i]范围内的word1转化成[0,j]范围内的word2需要多少步操作
    //当word1[i]==word2[j]时，说明当前两个位置的字母相等，需要看小范围内需要多少步操作
    //当word1[i]！=word2[j]时，说明当前位置需要操作一次，此时需要判断小范围内怎样操作步数最少
    //dp[i+1][j]代表替换word2第j个位置的元素，相当于word1新增一个
    //dp[i][j+1]代表删除word1第i个位置的元素
    //dp[i][j]代表删除word1第i个位置的元素并且删除word2第j个位置的元素，相当于word1替换一个元素
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1,
                               vector<int>(word2.size()+1,0));
        //初始化dp
        //代表删除word1中的元素，也就是只有word1有元素
        for(int i=0;i<word1.size();++i){
            dp[i+1][0]=i+1;
        }
        //代表新增word1中的元素，也就是只有word2有元素
        for(int j=0;j<word2.size();++j){
            dp[0][j+1]=j+1;
        }
        for(int i=0;i<word1.size();++i){
            for(int j=0;j<word2.size();++j){
                //当前位置不需要操作
                if(word1[i]==word2[j]){
                    dp[i+1][j+1]=dp[i][j];
                }
                //当前位置需要操作，增删改选一个操作步数小的
                else{
                    dp[i+1][j+1]=min({dp[i][j],dp[i+1][j],dp[i][j+1]})+1;
                }
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

总结

需要将操作分成几个部分，word1增加相当于word2删除，word1替换相当于word1和word2都删除，这一步很重要

总结起来就是找他们的公共部分，找到了之后看不同的元素需要经过多少步骤才能变成一样
当前元素相等不用操作
当前元素不相等,从增删改中找到一个操作数少的元素