众搜科技做百度网站,机械行业网站模板,服装设计公司名称,网站维护是什么专业今天接触到了真正的距离#xff0c;但可以通过增删改操作来逼近。
问题1#xff1a;583. 两个字符串的删除操作 - 力扣#xff08;LeetCode#xff09;
给定两个单词 word1 和 word2 #xff0c;返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字…今天接触到了真正的距离但可以通过增删改操作来逼近。
问题1583. 两个字符串的删除操作 - 力扣LeetCode
给定两个单词 word1 和 word2 返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
思路该题关键在于理解删除删除操作即多走一步由之前的状态进行推导。首先dp[i][j]还是表示从s[i]到t[j]需要的步数初始化时是从0到s[i]所需删除元素故为i。通过观察易发现dp可由dp[i-1]j-1],dp[i-1][j],p[i][j-1]得出代码如下
class Solution {
public:int minDistance(string word1, string word2) {vectorvectorint dp(word1.size()1,vectorint(word2.size()1));for(int i 0;i word1.size();i) dp[i][0] i;for(int j 0;j word2.size();j) dp[0][j] j;for(int i 1; i word1.size();i){for(int j 1;j word2.size();j){if(word1[i-1] word2[j-1]) dp[i][j] dp[i-1][j-1];else dp[i][j] min(dp[i][j-1]1,dp[i-1][j]1);}}return dp[word1.size()][word2.size()]; }};
问题272. 编辑距离 - 力扣LeetCode
给你两个单词 word1 和 word2 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作
插入一个字符删除一个字符替换一个字符
思路该题一上来我就去寻找规律并没有尝试去真正理解增删改操作怎么去替代并且在绘制例子矩阵时也较为粗心导致最后找出来的规律是错误的。其实这类题目并没有什么套路想想怎样将题目允许的变化做相应操作即可具体代码如下
class Solution {
public:int minDistance(string word1, string word2) {vectorvectorint dp(word1.size()1,vectorint(word2.size()1));for(int i 0;i word1.size();i) dp[i][0] i;for(int j 0;j word2.size();j) dp[0][j] j;for(int i 1;i word1.size();i){for(int j 1;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][j-1],dp[i-1][j],dp[i-1][j-1]}) 1;}}return dp[word1.size()][word2.size()];}
};
