583.Delete Operation for Two Strings
Description
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.
这是一道非常有趣的题目，间接考察最长公共子序列的求解
最长公共子序列和之前做过的最长公共子串略有不同，子串要求字母必须相连，而子序列则没有这个要求，比如：
cnblog和belong，最长公共子序列是blog，而最长公共子串是lo
结合公式，所需的删除操作的次数=word1的长度+word2的长度-2*最长公共子序列的长度。我们首先需要求解除吧最长公共子序列的长度。
最简单的方法当然是使用递归，如果[0,i],[0,j]最后一个字符相同，则比较[0,i-1],[0,j-1]的最后一个字符，若不相同，则删去第i个或第j个字符后，返回长度更长的子序列，代码如下：
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));
}
}
但很不幸，这样得到的结果是TLE，所以还是要借助动态规划算法求解此类问题。
如果使用动态规划求解最长公共子序列，那么假设[0,i],[0,j]的最后一个字符匹配，则LCS的长度取决于第i-1和j-1个字符；如果不匹配，则需要进行错位比较，也就是说，LCS的长度取决于[i-1]或[j-1]（取较长的一个），代码如下：
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()];
}
}
这个算法的原理可见动图 https://leetcode.com/problems/delete-operation-for-two-strings/solution/
当然，也可以直接借助动态规划求解修改次数，思路和上面的方法差不多，用dp[i][j]表示要将两字符串删除至相等时的删除次数。代码如下：
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()];
}
}