LeetCode 583. 两个字符串的删除操作(动态规划)
发布日期:2021-07-01 03:25:18
浏览次数:3
分类:技术文章
本文共 1144 字,大约阅读时间需要 3 分钟。
1. 题目
给定两个单词 word1 和 word2,找到使得 word1 和 word2 相同所需的最小步数,每步可以删除任意一个字符串中的一个字符。
示例:输入: "sea", "eat"输出: 2解释: 第一步将"sea"变为"ea",第二步将"eat"变为"ea" 提示:给定单词的长度不超过500。给定单词中的字符只含有小写字母。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/delete-operation-for-two-strings 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 解题
类似题目:
class Solution { public: int minDistance(string word1, string word2) { int n1 = word1.size(), n2 = word2.size(), i, j; if(n1==0 || n2==0) return max(n1,n2); vector> dp(n1+1,vector (n2+1,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] = 1+min(dp[i][j-1],dp[i-1][j]); //不相等 //可以有两种方式,删除一个 j,然后次数+1,dp[i][j-1]+1 //或者删除一个 i,次数+1,dp[i-1][j]+1 //其实还有一个删除i,j,次数+2,dp[i-1][j-1]+2,不可能次数最少 } } } return dp[n1][n2]; }};
40 ms 12.1 MB
转载地址:https://michael.blog.csdn.net/article/details/106009461 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年04月30日 16时23分26秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Objective-C 内存管理 看这个就够啦
2019-05-03
IOS开发--微信支付
2019-05-03
iOS 微信支付 实用教程
2019-05-03
UIViewController的基本概念与生命周期
2019-05-03
最新方法制作自己的cocoapods开源框架的详细步骤
2019-05-03
Getting start with OCMock in you unit test
2019-05-03
李洪强和你一起学习前端之(1)Html基础
2019-05-03
李洪强iOS经典面试题142-第三方框架及其管理
2019-05-03
李洪强经典面试题38
2019-05-03
我们必须自学
2019-05-03
iOS应用内付费(IAP)开发步骤列表
2019-05-03
iOS-TextField知多少
2019-05-03
用javascript协助导入图片
2019-05-03
白话 Ruby 与 DSL 以及在 iOS 开发中的运用
2019-05-03
获取任意线程调用栈的那些事
2019-05-03
主线程中也不绝对安全的 UI 操作
2019-05-03
深入研究 Runloop 与线程保活
2019-05-03
Swift 4迁移总结:喜忧参半,新的起点
2019-05-03
iOS 版本更新(强制更新)检测问题
2019-05-03
项目在iOS11上遇到的小问题
2019-05-03