72编辑距离

题目

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

• 法一：动态规划

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n=word1.size(),m=word2.size();//记录单词的字符数
        //二维动态规划，由于n个字符有n+1个切割点，故dp数组的长宽分别是n+1和m+1
        vector<vector<int>> dp(n+1,vector<int>(m+1,0));
        //初始化第一列，word1的前i个字符转化为word2，而word2是全空的，故每次删除i个字符，即dp[i][0]=i
        for(int i=0;i<=n;i++)
            dp[i][0]=i;
        //初始化第一行，word1全空，转化为有j个字符发word2，故每次添加j个字符
        for(int j=0;j<=m;j++)
            dp[0][j]=j;
        //填dp数组
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
            	//如果word1[i]和word2[j]字符相同，则dp[i][j]=dp[i-1][j-1],等于两个字符串均回退一个字符时的最小编辑数
                if(word1[i-1]==word2[j-1]) dp[i][j]=dp[i-1][j-1];
                else{//如果两个字符不想等，分增删改三种情况
                	//如果是将word1处字符改为word2处字符:dp[i][j]=dp[i-1][j-1]+1
                	//如果是将word1处字符后面添加一个word2字符:dp[i][j]=dp[i][j-1]+1,此时j处字符已经被新添加的字符匹配了，故最小编辑数为dp[i][j-1]+1
                	//如果是将word1处的字符删除:dp[i][j]=dp[i-1][j]+1,i处的字符已经被删除，看i-1处的字符是否与j处的匹配，故最小编辑数为dp[i-1][j]+1
                	//三种情况都能将word1转化为word2，故取最小赋值给dp[i][j]
                    dp[i][j]=1+min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]));
                }
            }
        }
        return dp[n][m];//返回最小编辑数
    }
};
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

• 时间复杂度O(n^2)
• 空间复杂度O(n^2)
• 思路
  • dp[i][j]表示:将word1的前i个字符转化为word2的前j个字符所需要的最小编辑数
  • 状态转移方程
    • 详细请查看代码注释
    • 如果word1[i]和word2[j]字符相同，则dp[i][j]=dp[i-1][j-1],等于两个字符串均回退一个字符时的最小编辑数
    • 如果两个字符不想等，分增删改三种情况
      如果是将word1处字符改为word2处字符:dp[i][j]=dp[i-1][j-1]+1
      如果是将word1处字符后面添加一个word2字符:dp[i][j]=dp[i][j-1]+1,此时j处字符已经被新添加的字符匹配了，故最小编辑数为dp[i][j-1]+1
      如果是将word1处的字符删除:dp[i][j]=dp[i-1][j]+1,i处的字符已经被删除，看i-1处的字符是否与j处的匹配，故最小编辑数为dp[i-1][j]+1
      三种情况都能将word1转化为word2，故取最小赋值给dp[i][j]
• 法二：滚动数组，一维动态规划

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n=word1.size(),m=word2.size();
        vector<int> dp(m+1,0);//记录原二维数组中的当前行
        int upper_left=0; //辅助记录f[i-1][j-1]
        //初始化第一行
        for(int j=0;j<=m;j++)
            dp[j]=j;
        //填dp数组
        for(int i=1;i<=n;i++)
        {
            upper_left=dp[0];//初始化为未修改前的dp[0]，即dp[i-1][0]
            dp[0]=i;//修改dp数组当前行第一个元素
            for(int j=1;j<=m;j++)
            {
                int upper=dp[j];//记录尚未被修改的f[j]，即为当前for循环的下一个元素对应的dp[i-1][j-1]
                if(word1[i-1]==word2[j-1]) dp[j]=upper_left;//当前末尾字符相同
                else{//当前末尾字符不相同
                	//dp[j]对应dp[i-1][j],dp[j-1]对应dp[i][j-1],upper_left对应dp[i-1][j-1]
                    dp[j]=1+min(dp[j],min(upper_left,dp[j-1]));
                }
                upper_left=upper;//记录下一个元素的dp[i-1][j-1]
            }
        }
        return dp[m];//返回最小编辑数
    }
};

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

• 时间复杂度O(n^2)
• 空间复杂度O(n)