公司网站改版方案盛世,微博推广方法有哪些,app怎么开发制作,青岛专门做网站的公司目录 Leetcode583. 两个字符串的删除操作Leetcode72. 编辑距离 Leetcode583. 两个字符串的删除操作 文章链接#xff1a;代码随想录 题目链接#xff1a;583. 两个字符串的删除操作 思路#xff1a;直接记录需要改#xff08;增或删#xff09;几个#xff0c;也就是求不… 目录 Leetcode583. 两个字符串的删除操作Leetcode72. 编辑距离 Leetcode583. 两个字符串的删除操作 文章链接代码随想录 题目链接583. 两个字符串的删除操作 思路直接记录需要改增或删几个也就是求不公共的子序列
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 - 1][j - 1] 2, min(dp[i][j - 1] 1, dp[i - 1][j] 1));}}return dp[word1.size()][word2.size()];}
};也可以记录最长公共子序列再减
class Solution {
public:int minDistance(string word1, string word2) {vectorvectorint dp(word1.size() 1, vectorint(word2.size() 1));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] 1;else dp[i][j] max(dp[i][j - 1], dp[i - 1][j]);}}return word1.size() word2.size() - dp[word1.size()][word2.size()] * 2;}
};Leetcode72. 编辑距离 文章链接代码随想录 题目链接72. 编辑距离 思路和上一题相比差别在于多了替换因此dp[i - 1][j - 1] 只需要多加一步即可变为dp[i][j]。
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 1; 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 - 1][j - 1] 1, min(dp[i - 1][j] 1, dp[i][j - 1] 1));}}return dp[word1.size()][word2.size()];}
};第五十六天打卡今天给周老师写了个冰层项目进展耽误了一些学习进度加油
