https://leetcode.com/problems/edit-distance/description/
参考 CodeGanker:
我们维护的变量res[i][j]表示的是word1的前i个字符和word2的前j个字符编辑的最少操作数是多少。假设我们拥有res[i][j]前的所有历史信息,看看如何在常量时间内得到当前的res[i][j],我们讨论两种情况:
1)如果word1[i-1]=word2[j-1],也就是当前两个字符相同,也就是不需要编辑,那么很容易得到res[i][j]=res[i-1][j-1],因为新加入的字符不用编辑;
2)如果word1[i-1]!=word2[j-1],那么我们就考虑三种操作:
2.1) 如果是删除word1[i - 1],那么res[i][j]=res[i-1][j]+1,也就是取word1前i-1个字符和word2前j个字符的最好结果,然后一个删除操作;
2.2) 如果是删除word2[j - 1],那么res[i][j]=res[i][j-1]+1,道理同上面一种操作;
2.3) 如果是替换操作,那么类似于上面第一种情况,但是要加一个替换操作(因为word1[i-1]和word2[j-1]不相等),所以递推式是res[i][j]=res[i-1][j-1]+1。
上面列举的情况包含了所有可能性。
两点思考:
- 删除和插入操作对应的操作数是一样的;
"" => "abc" 进行插入操作
同“abc” => ""
进行删除操作,所需的操作数是一致的; - 删除操作应该是更容易维护和进行推导运算的。因为删除 word[index] 处的 char,继续向下进行 word[greaterThanIndex] 的 chars 可以继续进行;相反,对word index 处插入新的char,会使原来的 char 后移,word 位数增加,该 char 仍须继续被计算;
class Solution {
public int minDistance(String word1, String word2) {
if (word1 == null || word1.length() == 0) {
return (word2 == null) ? 0 : word2.length();
}
if (word2 == null || word2.length() == 0) {
return (word1 == null) ? 0 : word1.length();
}
int len1 = word1.length();
int len2 = word2.length();
int[][] dp = new int[len1 + 1][len2 + 1];
for (int i = 0; i <= len1; i++) {
dp[i][0] = i;
}
for (int j = 0; j <= len2; j++) {
dp[0][j] = j;
}
for (int i = 1; i <= len1; i++) {
char c1 = word1.charAt(i - 1);
for (int j = 1; j <= len2; j++) {
char c2 = word2.charAt(j - 1);
if (c1 == c2) {
dp[i][j] = dp[i - 1][j - 1];
} else {
int replace = dp[i - 1][j - 1] + 1; // replace c1 to c2 in word1
int delete = dp[i - 1][j] + 1; // delete c1 in word1 at (i - 1)
int insert = dp[i][j - 1] + 1; // delete c2 in word2 at (j - 1)
dp[i][j] = Math.min(Math.min(replace, delete), insert);
}
}
}
return dp[len1][len2];
}
}
From 九章:
Edit Distance
state: f[i][j]a的前i个字符“配上”b的前j个字符 最少要用几次编辑使得他们相等
function:
f[i][j] = MIN(f[i-1][j-1], f[i-1][j]+1, f[i][j-1]+1) // a[i] == b [j]
= MIN(f[i-1][j], f[i][j-1], f[i-1][j-1]) + 1 // a[i] != b[j] intialize: f[i][0] = i, f[0][j] = j
answer: f[a.length()][b.length()]
网友评论