一个门户网站源码,织梦音乐网站程序,wordpress登录微信插件,好玩的html代码代码随想录算法训练营第五十八天|583.两个字符串的删除操作 、72. 编辑距离 文章目录 代码随想录算法训练营第五十八天|583.两个字符串的删除操作 、72. 编辑距离[toc]583.两个字符串的删除操作求公共部分长度#xff1a;即最长公共子串 72. 编辑距离 583.两个字符串的删除操作…代码随想录算法训练营第五十八天|583.两个字符串的删除操作 、72. 编辑距离 文章目录 代码随想录算法训练营第五十八天|583.两个字符串的删除操作 、72. 编辑距离[toc]583.两个字符串的删除操作求公共部分长度即最长公共子串 72. 编辑距离
583.两个字符串的删除操作
题目链接583. 两个字符串的删除操作 - 力扣LeetCode
题目描述
给定两个单词 word1 和 word2 返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
示例 1
输入: word1 sea, word2 eat
输出: 2
解释: 第一步将 sea 变为 ea 第二步将 eat 变为 ea示例 2:
输入word1 leetcode, word2 etco
输出4提示
1 word1.length, word2.length 500word1 和 word2 只包含小写英文字母
求公共部分长度即最长公共子串
class Solution {
public:int minDistance(std::string word1, std::string word2) {std::vectorstd::vectorint dp(word1.size()1,std::vectorint (word2.size()1));// dp[i][k] 表示 word1 中前i个字符与 word2中前 k个字符的共同字符数目for(int i 1;iword1.size();i){for(int k 1;kword2.size();k){if(word1[i-1] word2[k-1]){dp[i][k] dp[i-1][k-1]1;}else{dp[i][k] std::max(dp[i-1][k],dp[i][k-1]);}}}return word1.size()word2.size()-dp[word1.size()][word2.size()]*2;}
};72. 编辑距离
题目链接72. 编辑距离 - 力扣LeetCode
题目描述
给你两个单词 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 500word1 和 word2 由小写英文字母组成
class Solution {
public:int minDistance(std::string word1, std::string word2) {std::vectorstd::vectorint dp(word1.size()1,std::vectorint (word2.size()1));// if(word1[i-1] word2[k-1]) dp[i][k] dp[i-1][k-1];// else dp[i][k] std::min({dp[i-1][k],dp[i][k-1],dp[i-1][k-1]})1;for(int i 0;iword2.size();i) dp[0][i] i;for(int i 1;iword1.size();i) dp[i][0] i;for(int i 1;iword1.size();i){for(int k 1;kword2.size();k){if(word1[i-1]word2[k-1]) dp[i][k] dp[i-1][k-1];else dp[i][k] std::min({dp[i-1][k-1],dp[i-1][k],dp[i][k-1]})1;}}return dp[word1.size()][word2.size()];}
};
