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

【LeetCode每日一题系列】编辑距离,第1张

前言
编辑距离,经典的动态规划问题,在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 casedp[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题 编辑距离

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/562876.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-02
下一篇 2022-04-02

发表评论

登录后才能评论

评论列表(0条)

保存