DeleteOperationForTwoStrings [source code]
public class DeleteOperationForTwoStrings {
static
/******************************************************************************/
class Solution {
public int minDistance(String word1, String word2) {
char[] ch1 = word1.toCharArray(), ch2 = word2.toCharArray();
int m = ch1.length, n = ch2.length;
int[][] dp = new int[m + 1][n + 1]; //index denotes length;
for (int i = 1; i < m + 1; i++) {
for (int j = 1; j < n + 1; j++) {
if (ch1[i - 1] == ch2[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 m + n - 2 * dp[m][n];
}
}
/******************************************************************************/
public static void main(String[] args) {
DeleteOperationForTwoStrings.Solution tester = new DeleteOperationForTwoStrings.Solution();
String[] inputs = {
"sea", "eat", "2",
};
for (int i = 0; i < inputs.length / 3; i++) {
String word1 = inputs[3 * i], word2 = inputs[1 + 3 * i];
int ans = Integer.parseInt(inputs[2 + 3 * i]);
System.out.println(Printer.separator());
int output = tester.minDistance(word1, word2);
System.out.println(
Printer.wrapColor(word1 + " AND " + word2, "magenta") +
" -> " + output +
Printer.wrapColor(", expected: " + ans, ans == output ? "green" : "red")
);
}
}
}
比较明显的一点是这个问题可以当做是跟LCS问题一个本质; 但是LCS的算法其实我也不会;
直接浅显的自己写一个DP行不行呢? 忘记之前总结的DP问题的套路了, 大概摸索着来: 首先, 表格的两个维度是什么? 多半是两个string的长度; 返回值是什么? 也就是表格的entry是什么定义? 这个暂时还想不到, 或许就是直接的target value? 那么DP Property怎么发现, 具体的来说, 比如我们把第一个string的长度减少了1之后, 得到的这个subsolution, 怎么回过头来获得补全这个1长度之后的solution?
在geeks4geeks上面搜了一下, 大概知道LCS怎么写了, 好像就是dinitz上课的时候讲过的一个问题; 尝试写写看;
最后发现这个问题其实很熟悉之后还是很快做出来了, 速度是60ms (72%), 还算是不错的; 这里稍微需要注意的是, 这里你表格的坐标最终是设计的是什么? 我刚开始是认为应该是end index, 毕竟这个很合情合理, 但是如果这样设计, 那么最后表格的大小就是m*n, 有一个问题是, 你怎么反映base case? 因为坐标最小只能取到0, 比如你i取到0的时候, 就是"s", 然后你"s"还要和"eat"的所有的sub去比较, 才能得到所有的entry的数值, 这个就很麻烦;
但是如果用长度来作为坐标, 这个问题其实就自动解决了: again, 坐标最小可以取到的是0, 而长度是0的时候的这个base case的结果我们是知道的, 直接就是0就可以了, 不需要转换;
注意, 我这里的0row和0column虽然没有explicit的初始化, 但是实际你自己写DP的时候是需要注意初始化的, 我这里只不过是利用了系统自带的默认初始值而已;
上课的时候说过, Bottom-Up的时候填表的顺序要注意一下, 具体的顺序应该是考虑一下recursion公式的写法; 这里的recursion公式你可以看一下, 一个是row-1, 一个是column-1, 所以最后我们只要保证row的顺序是从上到下, 然后column的顺序是从左到右就行了, 这个正好其实也就是默认的顺序;
这个是editorial2, 有memo的Top-Down的DP:
public class Solution {
public int minDistance(String s1, String s2) {
int[][] memo = new int[s1.length() + 1][s2.length() + 1];
return s1.length() + s2.length() - 2 * lcs(s1, s2, s1.length(), s2.length(), memo);
}
public int lcs(String s1, String s2, int m, int n, int[][] memo) {
if (m == 0 || n == 0)
return 0;
if (memo[m][n] > 0)
return memo[m][n];
if (s1.charAt(m - 1) == s2.charAt(n - 1))
memo[m][n] = 1 + lcs(s1, s2, m - 1, n - 1, memo);
else
memo[m][n] = Math.max(lcs(s1, s2, m, n - 1, memo), lcs(s1, s2, m - 1, n, memo));
return memo[m][n];
}
}
整体思路还是差不多的, again, 注意这里表格的坐标是长度而不是index;
editorial3就是把这个程序Bottom-Up写起来, 所以就是跟我的自己的代码是一个意思;
另外, 思考一个问题, 我们之前说过, DP/recursion问题, 返回值的设计要具有DP Property, 尤其是DP里面, 这个返回值往往对应的就是表格里面的entry; 这里的这个entry你设计的时候, 你有没有考虑过这个思路? 事实上, 因为我们这里表格里面放的其实是LCS的值, 所以一定程度上, 我们这里的这个DP也可以认为是饶了弯子的, 也就是并不是直接就把target value作为返回值;
这个是editorial4:
public class Solution {
public int minDistance(String s1, String s2) {
int[][] dp = new int[s1.length() + 1][s2.length() + 1];
for (int i = 0; i <= s1.length(); i++) {
for (int j = 0; j <= s2.length(); j++) {
if (i == 0 || j == 0)
dp[i][j] = i + j;
else if (s1.charAt(i - 1) == s2.charAt(j - 1))
dp[i][j] = dp[i - 1][j - 1];
else
dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[s1.length()][s2.length()];
}
}
这个看起来其实就是把上面的LCS算法稍微改写了一下算式, 但是实际上背后的思路不是完全一样, 这里entry里面放的就是直接target value; 当然这个选择好不好, 无从评价, 不过是一个思路;
注意这里base case的计算, 这个i + j用的很聪明; 另外他这里的坐标还是用的length而不是index: 这样可以加一个维度, 使得base case更好处理; 第二个branch的意思是, 结尾相同, 所以不需要删除; 最后一个branch的意思是, 末尾不match, 我们肯定要删除至少一个end, 所有有一个1+的部分, 然后至于这个1来自于哪个方向, 就看哪个方向的剩余部分贡献的number of deletion更小就行了;
editorial5就是在以上做法的一个继续的小优化: 二维的表格转化成为一个row就可以了;
public class Solution {
public int minDistance(String s1, String s2) {
int[] dp = new int[s2.length() + 1];
for (int i = 0; i <= s1.length(); i++) {
int[] temp=new int[s2.length()+1];
for (int j = 0; j <= s2.length(); j++) {
if (i == 0 || j == 0)
temp[j] = i + j;
else if (s1.charAt(i - 1) == s2.charAt(j - 1))
temp[j] = dp[j - 1];
else
temp[j] = 1 + Math.min(dp[j], temp[j - 1]);
}
dp=temp;
}
return dp[s2.length()];
}
}
这个也是可以想到的; 另外, 虽然看起来好像你算的时候, 往两个方向的回退都有, 但是实际上你真正用到的, 需要保存的, 只有一个row了, 这个观点以前也介绍过, 在一个iteration里面, 你能看见的其实是你的历史信息的新和旧两个版本, 所以只保存上一个row, 在计算的时候, 你其实是可以同时看到old row and new row的;
discussion上面大部分的解法都跟editorial这里的差不多, 这个是一个有意思的图片:
Since the only operation allowed is deletion, this problem actually becomes finding the longest common subsequence.
这句话表达的其实就是edit distance跟LCS之间的关系;
这个是另外一个基于LCS的解法, 不过他这里是优化到了O(N)空间的做法:
@ymd said in Short java DP solution O(n) space (48ms):
public int minDistance(String word1, String word2) {
int[] dp = new int[word2.length()];
int lcs = 0;
for(int i = 0; i < word1.length(); i++){
int cur_max = 1;
for(int j = 0; j < word2.length(); j++){
int temp = dp[j];
if(word2.charAt(j) == word1.charAt(i)) dp[j] = cur_max;
cur_max = Math.max(temp+1, cur_max);
lcs = Math.max(lcs, dp[j]);
}
}
return word1.length() - lcs + word2.length() - lcs;
}
Use O(n) space, in i-th iteration over word1, update max possible length of common subsequence end up with word1.charAt(i) in word2 and store in the dp array.
不过他这个解法我其实花了很长时间最后也是没有看懂, 他这里到底是背后是什么逻辑; 当然你可以说是, 他这里的逻辑就是根据普通的LCS的算法, 然后完成一个DP表格的优化, 但是仔细看了看好像不是这么简单? 我感觉这个人想出这个算法应该还是有一点自己的思路在里面的, 只不过他这个思路具体是什么, 暂时我还是有点看不懂;
除开这些discussion里面基本就没有特别好的算法了;
Problem 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.
Difficulty:Medium
Total Accepted:8.4K
Total Submissions:19K
Contributor: CDY_Saikou
Companies
google
Related Topics
string
Similar Questions
Edit Distance