这道题还是使用 DP 来做，具体的原理其实也不是太难，就是先写出状态转移方程，每一个状态表示word1[i]和word2[j]及它们之前的字符中需要修改的数目：
1
2
| dp[i][j]=dp[i-1][j-1] if word1[i]==word2[j]
dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1 if word1[i]!=word2[j]
|
这个方程可以由回溯法的公式得出，主要的含义就是如果两个数相等，那么它们就不用修改了，不然就需要考虑是第一个单词的被删除了一个字母（或者第二个单词添加了一个字母），对应dp[i-1][j]，还是第二个单词被删除了一个字母（或者第一个单词添加了一个字母）,对应dp[i][j-1]，还是某一个单词被修改了一个字母，然后两个单词字母相同，对应dp[i-1][j-1]
这个问题里最难的地方还有边界条件，需要仔细思考才能得出。
以dp[i][0]为例，如果word1[0]和word2中的所有字母都不同，那么dp[i][0]这一行对应的数字应该为i+1，但是一旦有一个相同，问题就来了，相同的那一位就不需要改了，所以对应数字应该-1，之后对应的数字也需要减一，但是如果遇到第二个相同的，是不需要减一的。所以，需要填充的数字至少也要是i，所以公式就变成了dp[i][0]=max(dp[i-1][0]+(word1[i]==word2[0]?0:1),i)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
int minDistance(string word1, string word2) {
if(word1.size()==0) return word2.size();
if(word2.size()==0) return word1.size();
int **dp=new int*[word1.size()];
for(int i=0;i<word1.size();i++){
dp[i]=new int[word2.size()];
for(int j=0;j<word2.size();j++){
dp[i][j]=0;
}
}
for(int i=0;i<word1.size();i++){
for(int j=0;j<word2.size();j++){
if(i==0 && j==0) dp[0][0]=word1[0]==word2[0]?0:1;
else if(i==0) dp[0][j]=max(dp[0][j-1]+(word1[0]==word2[j]?0:1),j);
else if(j==0) dp[i][0]=max(dp[i-1][0]+(word1[i]==word2[0]?0:1),i);
else{
if(word1[i]==word2[j]) dp[i][j]=dp[i-1][j-1];
else dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
}
}
}
return dp[word1.size()-1][word2.size()-1];
}
};
|