电子商务网站前台建设,wordpress圆圈特效,杭州网站排名,搜索引擎优化的核心及内容1. 题目
给定两个单词 word1 和 word2#xff0c;找到使得 word1 和 word2 相同所需的最小步数#xff0c;每步可以删除任意一个字符串中的一个字符。
示例#xff1a;
输入: sea, eat
输出: 2
解释: 第一步将sea变为ea找到使得 word1 和 word2 相同所需的最小步数每步可以删除任意一个字符串中的一个字符。
示例
输入: sea, eat
输出: 2
解释: 第一步将sea变为ea第二步将eat变为ea提示
给定单词的长度不超过500。
给定单词中的字符只含有小写字母。来源力扣LeetCode 链接https://leetcode-cn.com/problems/delete-operation-for-two-strings 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目 LeetCode 72. 编辑距离DP LeetCode 712. 两个字符串的最小ASCII删除和DP类似编辑距离 LeetCode 1143. 最长公共子序列动态规划
class Solution {
public:int minDistance(string word1, string word2) {int n1 word1.size(), n2 word2.size(), i, j;if(n10 || n20)return max(n1,n2);vectorvectorint dp(n11,vectorint(n21,INT_MAX));for(i 0; i n1; i)dp[i][0] i;//第二字符串长度为0需要删除第一个字符串多少个字符for(i 0; i n2; i)dp[0][i] i;for(i 1; i n1; i){for(j 1; j n2; j){if(word1[i-1]word2[j-1])//w1第i个字符和 w2第j个字符相等dp[i][j] dp[i-1][j-1];//需要删除的最少字符等于前面的else{dp[i][j] 1min(dp[i][j-1],dp[i-1][j]);//不相等//可以有两种方式删除一个 j然后次数1dp[i][j-1]1//或者删除一个 i次数1dp[i-1][j]1//其实还有一个删除i,j次数2dp[i-1][j-1]2不可能次数最少}}}return dp[n1][n2];}
};40 ms 12.1 MB
