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删除和