Google+ Followers

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

[解题思路]
刚看到这个题的时候,首先想到的是求最大公共子串,然后用最长字符串的长度减去最大公共子串长度,并写了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
    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做了交换。

总的来说,这题比较有意思,但是也犯了很多可笑的错误。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:  }   
Post a Comment