LeetCode 72 Edit Distance

Posted on | In | 阅读

编辑距离推导，动态规划。

给定两个字符串s、t，用增加、删除、替换三种操作，使得s变成t的最少次数。

动态规划，dp[i][j]表示s前i个字符变为t的前j个字符的编辑距离。

初始化：dp[0][j] = j, dp[i][0] = i

递推分为两种情况：

  1. s[i] == t[j]

    dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1])

    分别对应删掉s[i]再变为t，s变为t[0: j-1]再加上t[j]，以及s[0: i-1]变为t[0: j-1]

    但是，第一种情况可以改为直接将s[0: i-1]变为t，然后将t[j]去掉(因为s[i]还保留着)，步数不变并且不少于s[0: i-1]变为t[0: j-1]。同理可证第二种情况的步数不少于s[0: i-1]变为t[0: j-1]。所以只需要从最后一种情况进行更新就行。

  2. s[i] != t[j]

    dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1)

    分别对应删掉s[i]再变为t，s变为t[0: j-1]再加上t[j]，以及s[0: i-1]变为t[0: j-1]再替换s[i]

C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        vector<vector<int> > dp;
        for(int i = 0; i <= len1; i++){
            vector<int> dpi;
            for(int j = 0; j <= len2; j++){
                if(i == 0){
                    dpi.push_back(j);
                }else if(j == 0){
                    dpi.push_back(i);
                }else{
                    dpi.push_back(0);
                }
            }
            dp.push_back(dpi);
        }
        for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; j++){
                if(word1[i-1] == word2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    int mi = min(dp[i-1][j], dp[i][j-1]);
                    mi = min(mi, dp[i-1][j-1]);
                    dp[i][j] = mi + 1;
                }
            }
        }
        return dp[len1][len2];
    }
};