72.Edit Distance---dp

时间:2023-03-08 21:34:59

题目链接:https://leetcode.com/problems/edit-distance/description/

题目大意:找出两个字符串之间的编辑距离(每次变化都只消耗一步)。

法一(借鉴):经典dp。代码如下(耗时15ms):

     //dp公式:dp[i][j]表示第一个字符串前i个字符到第二个字符串前j个字符的编辑距离长度
//当word1[i]==word2[j]时,dp[i][j]=dp[i-1][j-1]
//否则,dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
public int minDistance(String word1, String word2) {
int len1 = word1.length(), len2 = word2.length();
int dp[][] = new int[len1+1][len2+1];
//初始化
for(int i = 0; i <= len1; i++) {
dp[i][0] = i;
}
for(int i = 0; i <= len2; i++) {
dp[0][i] = i;
}
for(int i = 1; i <= len1; i++) {//下标从1开始
for(int j = 1; j <= len2; j++) {
if(word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
}
else {
int min = Integer.MAX_VALUE;
if(min > dp[i - 1][j - 1]) {
min = dp[i - 1][j - 1];
}
if(min > dp[i][j - 1]) {
min = dp[i][j - 1];
}
if(min > dp[i - 1][j]) {
min = dp[i - 1][j];
}
dp[i][j] = min + 1;
}
}
}
return dp[len1][len2];
}

dp数组变化(例子:abc到acde的编辑距离):

0 1("a") 2("c") 3("d") 4("e")
1("a") 0(a->a) 1(a->ac) 2(a->acd) 3(a->acde)
2("b") 1(ab->a) 1(ab->ac) 2(ab->acd) 3(ab->acde)
3("c") 2(abc->a) 1(abc->ac) 2(abc->acd) 3(abc->acde)

从上表可清楚看见最后结果在dp[3][4]中。

dp数组填充顺序:从左上到右下,即每一次数值计算都要用到左边,上边,左上的数据。