怎么网站定制,自己做网站卖视频,个人电脑做服务器网站,做厨具公司网站两个字符串的删除操作
给定两个单词 word1 和 word2 #xff0c;返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。 示例 1#xff1a;
输入: word1 sea, word2 eat
输出: 2
解释: 第一步将 sea…两个字符串的删除操作
给定两个单词 word1 和 word2 返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。 示例 1
输入: word1 sea, word2 eat
输出: 2
解释: 第一步将 sea 变为 ea 第二步将 eat 变为 ea示例 2:
输入word1 leetcode, word2 etco
输出4
思路 /* dp[i][j]表示以i-1为结尾的word1和以j-1为结尾的word2相同的最小删除的次数 相同 dp[i][j] dp[i-1][j-1]; 不同 dp[i][j] min(dp[i-1][j]1,dp[i][j-1]1,dp[i-1][j-1]2); 初始化dp[i][0] i; dp[0][j] j; 遍历顺序 从左到右从前到后 打印dp数组 */
代码
class Solution {
public:int minDistance(string word1, string word2) {/*dp[i][j]表示以i-1为结尾的word1和以j-1为结尾的word2相同的最小删除的次数相同dp[i][j] dp[i-1][j-1];不同dp[i][j] min(dp[i-1][j]1,dp[i][j-1]1,dp[i-1][j-1]2);初始化dp[i][0] i; dp[0][j] j;遍历顺序 从左到右从前到后打印dp数组*/vectorvectorintdp(word1.size()1,vectorint(word2.size()1,0));for(int i 0;iword1.size();i){dp[i][0] i;}for(int j 0;jword2.size();j){dp[0][j] j;}for(int i 1;iword1.size();i){for(int j 1;jword2.size();j){if(word1[i-1]word2[j-1])dp[i][j] dp[i-1][j-1];elsedp[i][j] min(min(dp[i-1][j]1,dp[i][j-1]1),dp[i-1][j-1]2);}}return dp[word1.size()][word2.size()];}
};
72. 编辑距离
给你两个单词 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)
思路 /* dp[i][j]表示以i-1的word1,j-1的word2的相同的最小步数dp[i][j] word1[i-1]word2[j-1] dp[i][j] dp[i-1][j-1]; word1[i-1]!word2[j-1] 增可以用删的逆行实现 删dp[i][j] min(dp[i-1][j]1,dp[i][j-1]1); 换dp[i][j] dp[i-1][j-1]1; 初始化 dp[i][0] i;dp[0][j] j; 遍历顺序 从左到右从前到后 打印dp数组 */
代码
class Solution {
public:int minDistance(string word1, string word2) {/*dp[i][j]表示以i-1的word1,j-1的word2的相同的最小步数dp[i][j]word1[i-1]word2[j-1]dp[i][j] dp[i-1][j-1];word1[i-1]!word2[j-1]增可以用删的逆行实现删dp[i][j] min(dp[i-1][j]1,dp[i][j-1]1);换dp[i][j] dp[i-1][j-1]1;初始化 dp[i][0] i;dp[0][j] j;遍历顺序 从左到右从前到后打印dp数组*/vectorvectorintdp(word1.size()1,vectorint(word2.size()1,0));for(int i 0;iword1.size()1;i){dp[i][0] i;}for(int j 0;jword2.size()1;j){dp[0][j] j;}for(int i 1;iword1.size()1;i){for(int j 1;jword2.size()1;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[word1.size()][word2.size()];}
};
还有很多瑕疵还需继续坚持
