[LeetCode] 583. Delete Operation for Two Strings 两个字符串的删除操作
2024-08-29 05:53:33
Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.
Example 1:
Input: "sea", "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".
Note:
- The length of given words won't exceed 500.
- Characters in given words can only be lower-case letters.
求出最长相同子序列Longest Common Subsequence,然后两个单词长度和减去2倍的相同子序列长度就是答案。
解法1: 递归, 如果[0, i], [0, j]最后一个字符相同,则比较[0, i-1], [0, j-1]的最后一个字符,若不相同,则删去第i个或第j个字符后,返回长度更长的子序列。TLE
解法2:动态规划dp,dp[i][j]表示word1的前i个字符和word2的前j个字符组成的两个单词的最长公共子序列的长度。如果当前的两个字符相等,那么dp[i][j] = dp[i-1][j-1] + 1 , 假设[0,i],[0,j]的最后一个字符匹配,则LCS的长度取决于第i-1和j-1个字符;如果不匹配,则需要进行错位比较,也就是说,LCS的长度取决于[i-1]或[j-1](取较长的一个)
Java1:
public class Solution {
public int minDistance(String s1, String s2) {
return s1.length() + s2.length() - 2 * lcs(s1, s2, s1.length(), s2.length());
}
public int lcs(String s1, String s2, int m, int n) {
if (m == 0 || n == 0)
return 0;
if (s1.charAt(m - 1) == s2.charAt(n - 1))
return 1 + lcs(s1, s2, m - 1, n - 1);
else
return Math.max(lcs(s1, s2, m, n - 1), lcs(s1, s2, m - 1, n));
}
}
Java2:
class Solution {
public int minDistance(String word1, String word2) {
int dp[][]=new int[word1.length()+1][word2.length()+1];
for(int i=0;i<word1.length()+1;++i){
for(int j=0;j<word2.length()+1;++j){
if(i==0||j==0)
continue;
if(word1.charAt(i-1)==word2.charAt(j-1))
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
}
}
return word1.length()+word2.length()-2*dp[word1.length()][word2.length()];
}
}
Java:
class Solution {
public int minDistance(String word1, String word2){
int dp[][]=new int[word1.length()+1][word2.length()+1];
for(int i=0;i<=word1.length();++i){
for(int j=0;j<=word2.length();++j){
if(i==0||j==0)
dp[i][j]=i+j;
else if(word1.charAt(i-1)==word2.charAt(j-1))
dp[i][j]=dp[i-1][j-1];
else
dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+1;
}
}
return dp[word1.length()][word2.length()];
}
}
Python1:
class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
return len(word1) + len(word2) - 2 * self.lcs(word1, word2) def lcs(self, word1, word2):
len1, len2 = len(word1), len(word2)
dp = [[0] * (len2 + 1) for x in range(len1 + 1)]
for x in range(len1):
for y in range(len2):
dp[x + 1][y + 1] = max(dp[x][y + 1], dp[x + 1][y])
if word1[x] == word2[y]:
dp[x + 1][y + 1] = dp[x][y] + 1
return dp[len1][len2]
Python2:
class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
m, n = len(word1), len(word2)
dp = [[0] * (n+1) for _ in xrange(2)]
for i in xrange(m):
for j in xrange(n):
dp[(i+1)%2][j+1] = max(dp[i%2][j+1], \
dp[(i+1)%2][j], \
dp[i%2][j] + (word1[i] == word2[j]))
return m + n - 2*dp[m%2][n]
C++:
class Solution {
public:
int minDistance(string word1, string word2) {
int n1 = word1.size(), n2 = word2.size();
vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, 0));
for (int i = 1; i <= n1; ++i) {
for (int j = 1; j <= n2; ++j) {
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return n1 + n2 - 2 * dp[n1][n2];
}
};
C++:
class Solution {
public:
int minDistance(string word1, string word2) {
int n1 = word1.size(), n2 = word2.size();
vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, 0));
for (int i = 0; i <= n1; ++i) dp[i][0] = i;
for (int j = 0; j <= n2; ++j) dp[0][j] = j;
for (int i = 1; i <= n1; ++i) {
for (int j = 1; j <= n2; ++j) {
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[n1][n2];
}
};
类似题目:
[LeetCode] 712. Minimum ASCII Delete Sum for Two Strings 两个字符串的最小ASCII删除和
All LeetCode Questions List 题目汇总
最新文章
- CentOS6上无法启动NFS服务
- soap缓存问题
- Oracle自动统计信息的收集原理及实验
- tuple内部方法
- spring中注解的通俗解释
- NDK(3)java.lang.UnsatisfiedLinkError: Native method not found解决方法
- STL笔记(3) copy()之绝版应用
- cpoint
- iOS开发之深入探讨runtime机制01-类与对象
- Java知识点:琐碎知识点(2)
- vim: 搭建vim看代码的环境
- Linux下php安装memcache
- 简单总结几种常见web攻击手段及其防御方式
- Using variables inside Postman and Collection Runner
- Redis学习笔记(2)——Redis的下载安装部署
- json 解析错误的问题
- ucos中的中断管理
- SpringBoot(十):读取application.yml下配置参数信息,java -jar启动时项目修改参数
- Java高级类特性(二)
- [转] h5上传视频或文件编写