这道题同样是一道 DP 问题，需要借助求最长公共子序列的方法的问题来解决。求出最长公共自序列以后，求将非公共子序列的字符删除需要的长度，就可以得到结果了。
最长公共子序列的递推公式为：
1
2
| dp[i][j]=dp[i-1][j-1]+1 if word1[i]==word2[j]
dp[i][j]=max(dp[i-1][j],dp[i][j-1]) if word1[i]!=word2[j]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| 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 i=0;i<word1.size();i++){
for(int j=0;j<word2.size();j++){
if(i==0 && j==0) dp[i][j]=word1[i]==word2[i]?1:0;
else if(i==0) dp[i][j]=max(dp[i][j-1],word1[i]==word2[j]?1:0);
else if(j==0) dp[i][j]=max(dp[i-1][j],word1[i]==word2[j]?1:0);
else{
if(word1[i]==word2[j]) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
int commonLen=dp[word1.size()-1][word2.size()-1];
return word1.size()+word2.size()-2*commonLen;
}
};
|