- 两个字符串的删除操作
给定两个单词 word1 和 word2,找到使得 word1 和 word2 相同所需的最小步数,每步可以删除任意一个字符串中的一个字符。(力扣)
示例
输入: “sea”, “eat”
输出: 2
解释: 第一步将"sea"变为"ea",第二步将"eat"变为"ea"
提示:
给定单词的长度不超过500。 给定单词中的字符只含有小写字母。
题目大意:删除两个单词不需要的字母,使剩下的部分相同。
我第一次看到这题,想到了之前求最大公共子序列的算法,求出了最大长度,用总长度来减去这个长度的两倍就是该题的解了,有递归树法,有动态规划(其实算法思想大致都差不多),但就在我用递归树的思想提交代码后,才运行了23个示例就提示我时间超限
解法一:
class Solution {
public int minDistance(String word1, String word2) {
int m=word1.length(),n=word2.length();
int k=f(word1,word2);
return m+n-2*k;
}
public static int f(String s1,String s2) {
if(s1.length()==0 || s2.length()==0) return 0;
if(s1.charAt(0)==s2.charAt(0)) {
return f(s1.substring(1),s2.substring(1))+1;
}
else {
return Math.max(f(s1.substring(1),s2), f(s1,s2.substring(1)));
}
}
}
解法二:
class Solution {
public int minDistance(String word1, String word2) {
int m=word1.length(),n=word2.length();
int dp[][] = new int[m+1][n+1];
for(int i=1;i<=m;i++) {
char cs=word1.charAt(i-1);
for(int j=1;j<=n;j++) {
char ct=word2.charAt(j-1);
if(cs==ct) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]);
}
}
return n+m-2*dp[m][n];
}
}
![在这里插入图片描述](https://img-blog.csdnimg.cn/0e19b0a93ba84ae19c03df6f7a01cb20.png)
内容源自:力扣网
https://leetcode.cn/problems/delete-operation-for-two-strings/
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)