Tuesday, November 25, 2014

[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

思路:

很多算法教科书上都有的经典二维DP问题。

1. 状态:
DP[i+1][j+1]:word1[0:i] -> word2[0:j]的edit distance。

2. 通项公式:
考虑word1[0:i] -> word2[0:j]的最后一次edit。无非题目中给出的三种方式:

a) 插入一个字符:word1[0:i] -> word2[0:j-1],然后在word1[0:i]后插入word2[j]
DP[i+1][j+1] = DP[i+1][j]+1

b) 删除一个字符:word1[0:i-1] -> word2[0:j],然后删除word1[i]
DP[i+1][j+1] = DP[i][j+1]+1

c) 替换一个字符:word1[0:i-1] -> word2[0:j-1]
word1[i] != word2[j]时,word1[i] -> word2[j]:DP[i+1][j+1] = DP[i][j] + 1
word1[i] == word2[j]时:DP[i+1][j+1] = DP[i][j] 

所以min editor distance应该为:
DP[i+1][j+1] = min(DP[i][j] + k, DP[i+1][j]+1, DP[i][j+1]+1) 
word1[i]==word2[j] -> k = 0, 否则k = 1

3. 计算方向:
replace (i, j)      delete (i, j+1)
insert (i+1, j)    (i+1, j+1)

可见要求DP[i+1][j+1],必须要知道二维矩阵中左上,上方和下方的3个值。所以当我们确定第0行和第0列的值后,就可以从上到下、从左到右的计算了。

4. 起始、边界值
DP[0][i] = i: word1为空,要转化到word2[0:i-1],需要添加i个字符。
DP[i][0] = i: word2为空,要从word1转化到空字符串,需要删除i个字符。



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for(int j=1; j<=n; j++)
            dp[0][j] = j;
        
        for(int i=1; i<=m; i++) {
            dp[i][0] = i;
            for(int j=1; j<=n; j++) {
                dp[i][j] = dp[i-1][j-1];
                if(word1[i-1]!=word2[j-1]) dp[i][j]++;
                dp[i][j] = min(min(dp[i-1][j]+1, dp[i][j-1]+1), dp[i][j]);
            }
        }
        
        return dp[m][n];
    }
};

2 comments:

  1. 行了,哥们儿,你的解释比大多算法教科书上的简洁明了的太多太多了!

    ReplyDelete
  2. 太棒了,一看就明白了

    ReplyDelete