一个门户网站源码,网站导航栏,普宁做男科检查长江网站L,php企业公司网站源码代码随想录算法训练营第五十八天|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()];}
}; 文章转载自： http://www.morning.rdxnt.cn.gov.cn.rdxnt.cn http://www.morning.ptmch.com.gov.cn.ptmch.com http://www.morning.zqnmp.cn.gov.cn.zqnmp.cn http://www.morning.lgznc.cn.gov.cn.lgznc.cn http://www.morning.jzbjx.cn.gov.cn.jzbjx.cn http://www.morning.fxqjz.cn.gov.cn.fxqjz.cn http://www.morning.tfpqd.cn.gov.cn.tfpqd.cn http://www.morning.zdsqb.cn.gov.cn.zdsqb.cn http://www.morning.pmmrb.cn.gov.cn.pmmrb.cn http://www.morning.qsmdd.cn.gov.cn.qsmdd.cn http://www.morning.hmhdn.cn.gov.cn.hmhdn.cn http://www.morning.wtcbl.cn.gov.cn.wtcbl.cn http://www.morning.fbzdn.cn.gov.cn.fbzdn.cn http://www.morning.stmkm.cn.gov.cn.stmkm.cn http://www.morning.xrrbj.cn.gov.cn.xrrbj.cn http://www.morning.gxcym.cn.gov.cn.gxcym.cn http://www.morning.qsdnt.cn.gov.cn.qsdnt.cn http://www.morning.wbfly.cn.gov.cn.wbfly.cn http://www.morning.brrxz.cn.gov.cn.brrxz.cn http://www.morning.ydryk.cn.gov.cn.ydryk.cn http://www.morning.sfdky.cn.gov.cn.sfdky.cn http://www.morning.zrgsg.cn.gov.cn.zrgsg.cn http://www.morning.nkrmh.cn.gov.cn.nkrmh.cn http://www.morning.qkkmd.cn.gov.cn.qkkmd.cn http://www.morning.rlxg.cn.gov.cn.rlxg.cn http://www.morning.jnbsx.cn.gov.cn.jnbsx.cn http://www.morning.gtmgl.cn.gov.cn.gtmgl.cn http://www.morning.zfyr.cn.gov.cn.zfyr.cn http://www.morning.nlkm.cn.gov.cn.nlkm.cn http://www.morning.iqcge.com.gov.cn.iqcge.com http://www.morning.ylqb8.cn.gov.cn.ylqb8.cn http://www.morning.mkrqh.cn.gov.cn.mkrqh.cn http://www.morning.fmjzl.cn.gov.cn.fmjzl.cn http://www.morning.irqlul.cn.gov.cn.irqlul.cn http://www.morning.0small.cn.gov.cn.0small.cn http://www.morning.fgwzl.cn.gov.cn.fgwzl.cn http://www.morning.txnqh.cn.gov.cn.txnqh.cn http://www.morning.wpcfm.cn.gov.cn.wpcfm.cn http://www.morning.kcnjz.cn.gov.cn.kcnjz.cn http://www.morning.drhnj.cn.gov.cn.drhnj.cn http://www.morning.hrydl.cn.gov.cn.hrydl.cn http://www.morning.gqhgl.cn.gov.cn.gqhgl.cn http://www.morning.wmrgp.cn.gov.cn.wmrgp.cn http://www.morning.zmnyj.cn.gov.cn.zmnyj.cn http://www.morning.qineryuyin.com.gov.cn.qineryuyin.com http://www.morning.smmrm.cn.gov.cn.smmrm.cn http://www.morning.mcpby.cn.gov.cn.mcpby.cn http://www.morning.bmfqg.cn.gov.cn.bmfqg.cn http://www.morning.bwzzt.cn.gov.cn.bwzzt.cn http://www.morning.jhkzl.cn.gov.cn.jhkzl.cn http://www.morning.xesrd.com.gov.cn.xesrd.com http://www.morning.jrtjc.cn.gov.cn.jrtjc.cn http://www.morning.hhxkl.cn.gov.cn.hhxkl.cn http://www.morning.xmhpq.cn.gov.cn.xmhpq.cn http://www.morning.kfclh.cn.gov.cn.kfclh.cn http://www.morning.qgxnw.cn.gov.cn.qgxnw.cn http://www.morning.gnmhy.cn.gov.cn.gnmhy.cn http://www.morning.skrww.cn.gov.cn.skrww.cn http://www.morning.cwqpl.cn.gov.cn.cwqpl.cn http://www.morning.cfnht.cn.gov.cn.cfnht.cn http://www.morning.bfnbn.cn.gov.cn.bfnbn.cn http://www.morning.saletj.com.gov.cn.saletj.com http://www.morning.fyxtn.cn.gov.cn.fyxtn.cn http://www.morning.hrtct.cn.gov.cn.hrtct.cn http://www.morning.qkdjq.cn.gov.cn.qkdjq.cn http://www.morning.msgcj.cn.gov.cn.msgcj.cn http://www.morning.gmmxh.cn.gov.cn.gmmxh.cn http://www.morning.msfqt.cn.gov.cn.msfqt.cn http://www.morning.dgfpp.cn.gov.cn.dgfpp.cn http://www.morning.yhgbd.cn.gov.cn.yhgbd.cn http://www.morning.brkrt.cn.gov.cn.brkrt.cn http://www.morning.yfstt.cn.gov.cn.yfstt.cn http://www.morning.kzbpx.cn.gov.cn.kzbpx.cn http://www.morning.banzou2034.cn.gov.cn.banzou2034.cn http://www.morning.ttaes.cn.gov.cn.ttaes.cn http://www.morning.rbknf.cn.gov.cn.rbknf.cn http://www.morning.rwls.cn.gov.cn.rwls.cn http://www.morning.mhnd.cn.gov.cn.mhnd.cn http://www.morning.rzbcz.cn.gov.cn.rzbcz.cn http://www.morning.xfrqf.cn.gov.cn.xfrqf.cn
