<>两个字符串的删除操作

<>动态规划

和1143相同,只要求出两个字符串的最长公共子序列长度即可,那么除了最长公共子序列之外的字符都是必须删除的,最后用两个字符串的总长度减去两个最长公共子序列的长度就是删除的最少步数。
class Solution { public: int minDistance(string word1, string word2) { vector<
vector<int>> dp(word1.size()+1 , vector<int>(word2.size()+1 ,0)); for(int i=0 ;i
<word1.size() ;i++) { for(int j=0 ;j<word2.size() ;j++) { if(word1[i] == word2[j
]) dp[i+1][j+1] = dp[i][j] + 1; else dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j]);
} } return word1.size() + word2.size() - 2*dp[word1.size()][word2.size()]; } };

技术
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信