?
动态规划：用dis[i][j]记录string1的前i个和string2的前j个的距离。那么可以知道：
?
1.如果str1的第i个，也就是str1[i-1]和str2的第j个也就是str2[j-1]相等的话，那么
?
dis[i][j] = dis[i-1][j-1]
?
2.如果str[i-1] != str2[j-1]
?
2.1 通过替换操作把str[i-1]替换成str2[j-1]，那么
?
dis[i][j] = dis[i-1][j-1] + 1;
?
2.2 通过插入操作在str1后面插入str2[j-1], 那么就相当于计算
?
dis[i][j] = dis[i][j-1] + 1;
?
2.3 通过插入操作在str2后面插入str1[i-1],那么就是
?
dis[i][j] = dis[i-1][j] + 1;
?
在上述三个中选一个最小的。迭代更新。
?
代码如下：
?
复制代码
class Solution {
public:
? ? int minDistance(string word1, string word2) {
? ? ? ? int len1 = word1.size(), len2=word2.size();
? ? ? ? if (len1 == 0) return len2;
? ? ? ? if (len2 == 0) return len1;
? ? ? ? vector > dis(len1+1, vector(len2+1));
? ? ? ? for (int i = 0; i <= len1; ++i)
? ? ? ? {
? ? ? ? ? ? dis[i][0] = i;
? ? ? ? }
? ? ? ? for (int j = 1; j <= len2; ++j)
? ? ? ? {
? ? ? ? ? ? dis[0][j] = j;
? ? ? ? }
? ? ? ??
? ? ? ? for (int i = 1; i <= len1; ++i)
? ? ? ? ? ? for (int j = 1; j <= len2; ++j)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if (word1[i - 1] != word2[j - 1])
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? dis[i][j] = min(dis[i-1][j-1] + 1, dis[i-1][j] + 1);
? ? ? ? ? ? ? ? ? ? dis[i][j] = min(dis[i][j-1] + 1, dis[i][j]);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? ? dis[i][j] = dis[i-1][j-1];
? ? ? ? ? ? }
? ? ? ? return dis[len1][len2];
? ? }
};