## Thursday, December 20, 2012

### [LeetCode] Edit Distance 解题报告

Given 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
» Solve this problem

[解题思路]

dp[i][j] =  dp[i-1][j-1] +1  if (A[i] == B[j])
or = max(dp[i][j-1], dp[i-1][j]);

将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，情况稍微复杂一点，
1. 如果将c替换成d，编辑距离是somestr1变成somestr2的编辑距离 + 1，也就是d(i-1,j-1) + 1
2. 如果在c后面添加一个字d，编辑距离就应该是somestr1c变成somestr2的编辑距离 + 1，也就是d(i,j-1) + 1
3. 如果将c删除了，那就是要将somestr1编辑成somestr2d，距离就是d(i-1,j) + 1
4. 那最后只需要看着三种谁最小，就采用对应的编辑方案了。
递推公式出来了：
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做了交换。

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:  }
``````