You have the following 3 operations permitted on a word:
a) Insert a character b) Delete a character c) Replace a character
[解题思路]
刚看到这个题的时候，首先想到的是求最大公共子串，然后用最长字符串的长度减去最大公共子串长度，并写了code，但是随后测试case的时候，发现有问题。
比如A= “ab”， B="bc"， 最大子串为“b”， 长度为1。但是如果把A转成B，需要2步，减a加c。
可见，最长子串并没有考虑到子串的差异，有可能带来多个操作。
解法仍然是二维DP，只不过转换方程有变化。
如果是求最长子串，方程是：
dp[i][j] = dp[i-1][j-1] +1 if (A[i] == B[j])
or = max(dp[i][j-1], dp[i-1][j]);
初始条件： dp[0][j] = 0, dp[i][0] = 0
但对于编辑距离的话， 当我们要计算d(i,j)时，即计算A(i)到B(j)之间的编辑距离， 此时，设A(i)形式是somestr1c；B(i)形如somestr2d的话，
将somestr1变成somestr2的编辑距离已知是d(i-1,j-1)
将somestr1c变成somestr2的编辑距离已知是d(i,j-1) 将somestr1变成somestr2d的编辑距离已知是d(i-1,j) 那么利用这三个变量，就可以递推出d(i,j)了： 如果c==d，显然编辑距离和d(i-1,j-1)是一样的 如果c!=d，情况稍微复杂一点，
- 如果将c替换成d，编辑距离是somestr1变成somestr2的编辑距离 + 1，也就是d(i-1,j-1) + 1
- 如果在c后面添加一个字d，编辑距离就应该是somestr1c变成somestr2的编辑距离 + 1，也就是d(i,j-1) + 1
- 如果将c删除了，那就是要将somestr1编辑成somestr2d，距离就是d(i-1,j) + 1
那最后只需要看着三种谁最小，就采用对应的编辑方案了。
递推公式出来了：
dp[i][j] = dp[i-1][j-1] if (A[i] == B[j])
or = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) +1;
初始条件： dp[0][j] = j and dp[i][0] = i [Code] 也可以用二维数组，这里我用两个滚动数组来计算了。省事。
1: int minDistance(string word1, string word2) { 2: // Start typing your C/C++ solution below 3: // DO NOT write int main() function 4: if(word1.size() < word2.size()) 5: word1.swap(word2); 6: string& bigStr = word1; 7: string& smallStr = word2; 8: int * matchUp = new int[20000]; 9: int* matchDown = new int[20000]; 10: for(int i=0; i<= smallStr.size(); i++) 11: { 12: matchUp[i] = 0; 13: matchDown[i] = i; 14: } 15: for(int i=1; i<=bigStr.size(); i++) 16: { 17: matchUp[0] = i; 18: for(int j= 1; j<=smallStr.size(); j++) 19: { 20: if(bigStr[i-1] == smallStr[j-1]) 21: { 22: matchUp[j] = matchDown[j-1]; 23: } 24: else 25: { 26: matchUp[j] = min(matchDown[j], matchDown[j-1]); 27: matchUp[j] = min(matchUp[j], matchUp[j-1]) +1; 28: } 29: } 30: int* temp = matchUp; 31: matchUp = matchDown; 32: matchDown = temp; 33: } 34: return matchDown[smallStr.size()]; 35: } [已犯错误] 1. Line 4~7 关于交换字符串的实现，一开始的实现是 string& bigStr = word1.size() > word2.size()? word1: word2; string& smallStr = word1.size() < word2.size()? word1: word2; 这里的问题是，第一，如果word1 和word2的长度相等，则bigStr和smallStr都指向了word2. 然后， 改成了 string& bigStr = word1; string& smallStr = word2; if(word1.size() < word2.size()) { string& temp = bigStr; bigStr = smallStr; smallStr = temp; } 这里的问题，是对象的引用是没法交换的，这段代码的结果是，bigStr和smallStr都指向了word1 。要交换还得用指针。 2. Line 13, 17 初始条件。第17行，最初忘了写，结果老是过不了。 3. Line 20 最初版本是 (bigStr[i] == smallStr[j])，忽略了i，j作为长度的标识来使用，如果需要作为index来用，需要减1. 4. Line 34 最初版本是return matchUp[smallStr.size()]; 这个错误非常可笑，尤其是Line 30～32已经把matchUp和matchDown做了交换。 总的来说，这题比较有意思，但是也犯了很多可笑的错误。c++好久没碰了，很多概念都忘了。 Update: 7/2/2013. Remove unnecessory code 1: int minDistance(string word1, string word2) { 2: int * matchUp = new int[20000]; 3: int* matchDown = new int[20000]; 4: for(int i=0; i<= smallStr.size(); i++) 5: { 6: matchUp[i] = 0; 7: matchDown[i] = i; 8: } 9: for(int i=1; i<=word1.size(); i++) 10: { 11: matchUp[0] = i; 12: for(int j= 1; j<=word2.size(); j++) 13: { 14: if(word1[i-1] == word2[j-1]) 15: { 16: matchUp[j] = matchDown[j-1]; 17: } 18: else 19: { 20: matchUp[j] = min(matchDown[j], matchDown[j-1]); 21: matchUp[j] = min(matchUp[j], matchUp[j-1]) +1; 22: } 23: } 24: int* temp = matchUp; 25: matchUp = matchDown; 26: matchDown = temp; 27: } 28: return matchDown[word2.size()]; 29: }