[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

[解题思路]

刚看到这个题的时候，首先想到的是求最大公共子串，然后用最长字符串的长度减去最大公共子串长度，并写了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，情况稍微复杂一点，
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
那最后只需要看着三种谁最小，就采用对应的编辑方案了。
递推公式出来了：
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:  }