网站建设目标规划,淘宝客如何建设自己的网站,公司做网站计入什么科目,杰讯山西网站建设#x1f4dd;个人主页#xff1a;Sherry的成长之路 #x1f3e0;学习社区#xff1a;Sherry的成长之路#xff08;个人社区#xff09; #x1f4d6;专栏链接#xff1a;练题 #x1f3af;长路漫漫浩浩#xff0c;万事皆有期待 文章目录 两个字符串的删除操作编辑距… 个人主页Sherry的成长之路 学习社区Sherry的成长之路个人社区 专栏链接练题 长路漫漫浩浩万事皆有期待 文章目录 两个字符串的删除操作编辑距离总结 两个字符串的删除操作
583. 两个字符串的删除操作 - 力扣LeetCode
这道题也是对于编辑距离的铺垫题目是可以操作两个字符串的删除使得两个字符串的字符完全相同这道题可以用递推公式模拟删除也可以使用求两个字符串的最大公共子序列的解题方法求出最长的公共非连续子序列然后再用两个字符串本身的长度减去这个公共子序列长度也可以求出至少要删除几步。这里只分析第一种解题方法。
dp数组的含义dp【i】【j】表示以i-1为下标的字符串1和以j-1为结尾的字符串2要想使它们相等所要删除的最小步数是多少。
递推公式由于dp数值含义当字符串1的i-1为结尾的下标元素与字符串2以j-1为结尾的下标元素相等时dp【i】【j】dp【i-1】【j-1】。含义是当前元素相等那么到达当前的位置需要删除的步数就和上一个位置的所需步数相等因为此时元素相等没有删除元素。
第二种情况就是两个对应元素不相等这时又分为两种不同情况即两元素不等的时候删除第一个字符串的元素或者是删除第二个字符串的元素比较一下当前是哪一种删除的步数可以得到最小值。第一种就是删除字符串1的那个字符那就是dp【i-1】【j】1dp数组的定义是i-1和j-1的下标的所以此时j就代表前一个字符不变然后略过字符串1这个字符去向前找上一次的删除步数是多少第二种情况是删除字符串2自然就是dp【i】【j-1】1最后取最小值。
dp数组初始化初始化一般是看递推公式决定的当字符串1为空时候字符串2需要删除当前字符个数的步数才能达到空字符串也就是需要删除j个。当字符串2为空也是同样的道理字符串1需要删除i个。根据这一性质我们可以初始化第一行和第一列也就是两个分别是空字符串情况其他的部分统一初始化为0因为递推公式会全部覆盖。
遍历顺序根据递推公式可知从上到下从左到右。
class Solution {
public:int minDistance(string word1, string word2) {vectorvectorintdp(word1.size()1,vectorint(word2.size()1,0));dp[0][0]0;for(int i1;iword1.size();i)dp[i][0]i;for(int j1;jword2.size();j)dp[0][j]j;for(int i1;iword1.size();i){for(int j1;jword2.size();j){if(word1[i-1]word2[j-1])dp[i][j]dp[i-1][j-1];else dp[i][j]min(dp[i-1][j]1,dp[i][j-1]1);}}return dp[word1.size()][word2.size()];}
};编辑距离
72. 编辑距离 - 力扣LeetCode
编辑距离是一道困难题有了前面几期的铺垫这道题也能更容易理解一些这道题是求使两个字符串能变相等的最小操作数有几步题目要求可以使任意一个字符串增加一个字符或删除一个字符或替换该指定位置的字符看起来题目要求有一些复杂但是实际上还是较容易理解的主要是要弄懂递推公式的意义是什么。
dp数组的含义dp数组的含义是到第一个字符串i-1的位置和第二个字符串j-1位置为止所用最少的步数能使它们相等。
递推公式我们来看如果两对应下标字符对应相等那么就应该是当前的位置最少步数等于上一次对应下标的最少步数。 ifword1【i-1】word2【j-1】dp【i】【j】dp【i-1】【j-1】 如果两对应下标字符不等那么我们先来分析删除字符
根据往期的删除字符的操作即是当两个字符确认已经不等时候要么是不考虑字符1当前的字符而去考虑前一个位置要么就是不考虑字符2的当前字符去考虑它的前一个字符。然后取最小值。也就是dp【i-1】【j】和dp【i】【j-1】两者取最小值。那么增加字符怎么写呢这是关键实际上增加字符是和删除字符的递推公式是完全一样的。因为我们删除了字符串1的一个字符不就是相当于增加了字符串2的一个字符吗我们要增加的字符一定是我们所需要的字符也就是字符串2里没有的但是字符串1里有的反之同理所以说它们的操作本质上是一样的。那么还剩下最后一种情况就是交换两个字符串word1替换word1【i-1】或者word2替换word2【j-1】才能使两字符串相等回顾一下如果这两个字符相同的话那么在dp数组应表现为dp【i】【j】dp【i-1】【j-1】所以当他们不同而且此时又不是增删操作时候我们替换其中一个字符所用的最少步数应该是dp【i-1】【j-1】1。也就是说替换一个字符就可以让word1【i-1】和word2【j-1】相等。根据上面的推理我们得出结论递推公式就是他们三种情况取最小的方案。
dp数组的初始化dp数组初始化与上一道题思路是相同的当一个串是空串时那么另一个串就需要删除全部字符才能与之相等按照这一思路来初始化。
遍历顺序由递推公式可知遍历顺序是从左到右从上到下的。
class Solution {
public:int minDistance(string word1, string word2) {vectorvectorintdp(word1.size()1,vectorint(word2.size()1,0));for(int i0;iword1.size();i)dp[i][0]i;for(int j0;jword2.size();j)dp[0][j]j;for(int i1;iword1.size();i){for(int j1;jword2.size();j){if(word1[i-1]word2[j-1])dp[i][j]dp[i-1][j-1];else dp[i][j]min(dp[i-1][j-1]1,min(dp[i-1][j]1,dp[i][j-1]1));}}return dp[word1.size()][word2.size()];}
};重要的是要理清递推公式的思想其他的部分和以往做的题没有什么太大区别即使它是一道困难题。
总结
今天我们完成了两个字符串的删除操作、编辑距离两道题相关的思想需要多复习回顾。接下来我们继续进行算法练习。希望我的文章和讲解能对大家的学习提供一些帮助。 当然本文仍有许多不足之处欢迎各位小伙伴们随时私信交流、批评指正我们下期见~
