编辑距离

---

问题描述：leetcode:72Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character b) Delete a character c) Replace a character

给定两个字符串word1和word2;求把word1转化为word2需要的最少的步骤。对于字符串可以有以下操作：

a) 插入一个字符 b) 删除一个字符 c) 替换一个字符

思路：

先考虑边界情况，当word1有输入，word2为空时；所需要的步骤为word1的长度。

先考虑边界情况，当word1为空，word2有输入时；所需要的步骤为word2的长度。

当word1和word2都有输入时，对于dp[i][j]为何值取决于word1[i-1]与word2[j-1]是否相等，当不相等时：

dp[i][j] = dp[i-1][j] , dp[i][j-1], dp[i-1][j-1]中的最小值加1;

如下图所示： 由于a 与 d 不相等，所以dp[1][4]的值取决于图中所示三个值，取三个值中的最小值然后加1.

当word1[i-1]与word2[j-1]相等时： dp[i][j]＝dp[i-1][j-1]

如图所示：

---

我自己的渣代码，虽然AC但是可以看到一堆补丁：

int minDistance(string word1, string word2) { int row = word1.length(); int col = word2.length(); //如何使得可以根据row和col求得数组的大小 if(row==0&&col==0) return 0; else if(row==0) return col; else if(col==0) return row; int a = 0; int b = 0; int ans[row][col]; string::iterator rowbegin=word1.begin(); string::iterator colbegin=word2.begin(); for (string::iterator i=word2.begin(); i!=word2.end(); i++){ if (*i == *rowbegin) { ans[a][b] = b; } else if(b==0){ ans[a][b] = 1; } else{ ans[a][b] = ans[a][b-1]+1; } b++; } a = 1; b = 0; for (string::iterator j=word1.begin()+1; j!=word1.end(); j++){ if (*j == *colbegin) { ans[a][b] = a; } else{ ans[a][b] = ans[a-1][b]+1; } a++; } a = 1; b = 1; for (string::iterator i=rowbegin+1;i!=word1.end(); i++){ b = 1; for (string::iterator j=colbegin+1;j!=word2.end(); j++){ if (*i==*j) { ans[a][b] = ans[a-1][b-1]; } else{ ans[a][b] = min(min(ans[a-1][b],ans[a][b-1]),ans[a-1][b-1])+1; } b++; } a++; } return ans[row-1][col-1]; }

leetcode优秀代码：

int minDistance(string word1, string word2) { int m = word1.length(), n = word2.length(); vector<vector<int> > dp(m + 1, vector<int> (n + 1, 0)); for (int i = 1; i <= m; i++) dp[i][0] = i; for (int j = 1; j <= n; j++) dp[0][j] = j; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1]; else dp[i][j] = min(dp[i - 1][j - 1] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j] + 1)); } } return dp[m][n]; }

---

语法注意点：

string是可以使用str[i]来获取第i+1个字符的，不一定非得使用iterator：

if (word1[i - 1] == word2[j - 1]);

定义了一个二维数组，行列数都已知： 注意：最后两个 > >中间有个空格。

vector<vector<int> > dp(m + 1, vector<int> (n + 1, 0));

以上之所以要m+1和n+1是因为考虑到边界，当一个word没有输入时的情况；所以数组的大小要大一点。