【LeetCode每日一题系列】编辑距离

前言
编辑距离，经典的动态规划问题，在leetcode72题，属于困难题目。

编辑距离主要的困难在于思考如何去进行状态的转移与选择。

接下来，我们将一步一步分析，解决编辑距离的相关问题。

文章目录

• 题目描述
• 思路分析
• 初步代码
• 动态规划优化
• leetcode 结果展示
• • dp table
  • 递归备忘录解法
• 扩展延伸
• 总结

---

题目描述

给你两个单词 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 由小写英文字母组成

思路分析

编辑距离问题就是给定了两个字符串word1，word2，只能使用三种 *** 作即删除、插入、替换，将word1变成word2，求最少的 *** 作数。

其中，word1和word2两者之间的变换，无论是word1变换为Word2还是word2变换成word1，最短的编辑距离应该都是一样的。

因此，我们只需要考虑其中一种变换就可
解决双字符串动态规划问题，一般使用双指针i，j分别指向两个字符串的串尾，随后不断往前往前缩减，缩小问题的规模
接下来，我们简单看一下示例1中word1怎么转换为word2的

word1 = "horse", word2 = "ros"
word1: h o r s e
word2: r o s
================
1:
               i
word1: h o r s e
word2: r o s
           j
word1[i] != word2[j] 删除word1[j] i--  （第一次 *** 作）
================
2:
             i
word1: h o r s
word2: r o s
           j
word1[i] == word2[j] 跳过，i--,j--
=================
3：
           i
word1: h o r s
word2: r o s
         j  
word1[i] != word2[j] 删除word1[i]，i-- （第二次 *** 作）
==================
4:
         i
word1: h o s
word2: r o s
         j
word1[i] == word2[j] 跳过，i--,j--
==================
5:
       i
word1: h o s
word2: r o s
       j
word1[i] != word2[j] 替换word1[i]，i--,j--   （第三次 *** 作）
===================
6：
       i
word1: r o s
word2: r o s
       j
word1[i] != word2[j] 跳过，i--,j--
===================
i < 0 , j < 0 结束

根据上述步骤，我们发现其实字符串转换过程中，不止包含三个 *** 作，其实还有第4个 *** 作【跳过】，即什么都不做。

因为本身两个字符已经相同了，而我们为了使编辑距离尽可能的小，因此应该尽可能的补缺改动本来相同的字符。

另外除了上述可能的情况外，我们还需要考虑一个问题：i或者j提前走完了。

也就是说，其中一方多了部分字符串，此时只能采用删除或者插入方法不断的缩减两个字符串之间的差距。

看下方示例：

		 i
word1:   a r o s
word2:   r o s
	   j

上述两种i，j 提前走后属于是算法的base case

初步代码

动态规划 递归等常用方法，都需要考虑base case情况。

在上述介绍中，我们了解到base case就是 i 走完word1，或者j走完s2,可以直接返回另一个字符出剩下的长度。

同时，对于每对字符是word1[i] 和 word2[j] ，存在4中 *** 作方式：

if (word1[i] == word2[j]){
	skip;
	i++;j++;
}else{
	三选一：
	insert,
	delete,
	replace
}

针对这个代码框架，我们再来确定一下动态规划所必须的要素：状态以及选择。

状态即i，j位置，选择则是4种 *** 作skip，insert，delete，replace。

这里先提供算法代码，后面会对代码进行详细解释：

//dp函数的定义
//s1[0..i] 和 s1[0..j]的最小编辑距离是dp(i,j)
int dp(string s1,string s2,int i,int j){
	//base case 
	if(i == -1) return j + 1;
	if(j == -1) return i + 1;
	//做选择
	if(s1[i] == s2[j]){
		return dp(s1,s2,i-1,j-1);
	}else{
		return min(
			dp(s1,s2,i,j-1)+1,
			dp(s1,s2,i-1,j)+1,
			dp(s1,s2,i-1,j-1)+1
		);
	}
	return 0;
}
int minDistance(string s1,string s2){
	return dp(s1,s2,s1.length()-1,s2.length()-2);
}

接下来介绍该段代码实义，其中base case部分就不再赘述，主要解释选择部分代码。

其中dp(i,j)定义为：

dp(i,j)的返回值就是s1[0..i]和s2[0..j]的最小编辑距离

---

第一段代码解释
本来就相等的一对字符，为了获取最小的编辑距离，此时我们应该什么都不做。

s1[0..i]和s2[0..j]的最小编辑距离等于s1[0..i-1]和s2[0..j-1]的最小编辑距离

if(s1[i] == s2[j]) 
	return dp(s1,s2,i-1,j-1);

---

但是如果s1[i] != s2[j],则需要考虑三种 *** 作：

dp(s1,s2,i,j-1)+1;  //插入 *** 作
//解释：
/*直接在s1[i]中插入一个和s2[j]一样的字符；
  那么s2[j]就被匹配了，前移j，继续和i对比；
  同时别忘了给 *** 作数+1；
  如下案例所示：    s1[i] != s2[j]
			i   insert "p"
s1  r   a   d   l  e
s2  a   p   p   l  e
  			j

			i   
s1  r   a   d   p   l  e
s2  a   p   p   l   e
  		j
  			
*/

dp(s1,s2,i-1,j)+1; //删除 *** 作
//解释：
/*直接在s1[i]删除；
  前移i，继续和j对比；
  同时别忘了给 *** 作数+1；
  如下案例所示：  s1[i] != s2[j]
	i   delete "p"
s1  r   a   p   p	l  e
s2  a   p   p   l   e
 j

 i   
s1  a   p   p   l   e
s2  a   p   p   l   e
 j
  			
*/

dp(s1,s2,i-1,j-1)+1; //替换 *** 作
//解释：
/*直接在s1[i]替换s2[j]一样的字符；
  那么s2[j]就被匹配了，前移i和j；
  同时别忘了给 *** 作数+1；
  如下案例所示：    s1[i] != s2[j]
			i   replace"p"
s1  r   a   d   p  l  e
s2  a   p   p   l  e
  			j

		i   
s1  r   a   p   p   l  e
s2  a   p   p   l   e
  		j	
*/

动态规划优化

动态规划问题主要解决存在重叠子问题，而在上述递归框架算法中，很容易就可以看出重叠子问题：
针对子问题dp(i-1,j-1)，我们可以通过dp(i,j) 替换 *** 作 dp(i-1,j-1);dp(i,j) 删除 *** 作 dp(i ,j-1)，插入 *** 作dp(i-1,j-1)两条路径。

可以看出存在一条重复路径，那么一定存在大量的重复路径也就是重复子数组，因此我们利用备忘录形式将上述代码进行更新，保存子问题结果。

vector<vector<int>> memo(s1.length(),vector<int>(s2.length(),0));
int dp(string s1,string s2,int i,int j){
	//base case 
	if(i == -1) return j + 1;
	if(j == -1) return i + 1;
	if(memo[i][j] != 0) return memo[i][j];
	//做选择
	if(s1[i] == s2[j]){
		memo[i][j] =  dp(s1,s2,i-1,j-1);
	}else{
		memo[i][j] =  min(
			dp(s1,s2,i,j-1)+1,
			dp(s1,s2,i-1,j)+1,
			dp(s1,s2,i-1,j-1)+1
		);
	}
	return memo[i][j];
}

上述为备忘录结果，依照自顶向下递归的方式存储子问题。

接下来我们将讲解DP table解法，用于处理自底向上的方式解法。

dp数组为二维数组，其中dp[..][0],dp[0][..]分别对应递归中base case，dp[i][j]定义与上述函数类似：

int dp(int i,int j);
解释：返回s1[0…i] 和 s2[0…j]之间的编辑距离
dp[i][j];
解释：存储s1[0…i-1] 和 s2[0…j-1]之间的编辑距离

这里需要注意的是，dp函数的base case 是 i，j == -1，而数组索引至少为0，所以存在偏移1位。

数组大小应设为length+1；
下面看代码：

//dp函数的定义
//s1[0..i] 和 s1[0..j]的最小编辑距离是dp(i,j)
int dp(string s1,string s2,int i,int j){
	int m = s1.length(),n = s2.length();
	vector<vector<int>> dp(m+1,vector<int>(n+1,0)); //偏移1位，所以数组大小应该扩容1位
	//base case 
	for(int i = 1; i <= m;i++){
		dp[i][0] = i;
	}
	for(int j = 1; j <= n;j++){
		dp[0][j] = i;
	}
	for(int i = 1;i <= m;i++){
		for(int j = 1; j <= n;j++){
			if(s1[i] == s2[j]){
				dp[i][j] = dp[i-1][j-1];
			}else{
				dp[i][j] = min(min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+1);
			}
		}
	}
	return dp[m][n];
}
int minDistance(string s1,string s2){
	return dp(s1,s2,s1.length()-1,s2.length()-2);
}

leetcode 结果展示

dp table

class Solution {
public:
    //动态规划，自底向上解法

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

递归备忘录解法

class Solution {
public:
    //递归解法
    int minDp(string s1,string s2,int i,int j,vector<vector<int>>& memo){
        if(i == -1){
            return j+1;
        }
        if(j == -1){
            return i+1;
        }
        if(memo[i][j] != 0) return memo[i][j];
        
        if(s1[i] == s2[j]){
            memo[i][j] = minDp(s1,s2,i-1,j-1,memo);
        }else{
            int d1 = minDp(s1,s2,i-1,j,memo)+1;
            int d2 = minDp(s1,s2,i,j-1,memo)+1;
            int d3 = minDp(s1,s2,i-1,j-1,memo)+1;
            memo[i][j] = min(min(d1,d2),d3);
        }
        return memo[i][j];

    }
    int minDistance(string word1, string word2) {
        vector<vector<int>> memo(word1.size(),vector<int>(word2.size(),0));
        return minDp(word1,word2,word1.length()-1,word2.length()-1,memo);
    }   
};

扩展延伸

【此节代码用于将结果获取的结果以及 *** 作顺序进行打印，由于时间关系后续补充。

】

总结

[参考文献]：
《labuladong的算法小抄》
LeetCode 72题 编辑距离