leetcode-72-线性DP-编辑距离

发表于 | 分类于

题目

1.png

解法

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
// 递归 + 备忘录
class Solution {
public:
    typedef tuple<int, int> key;

    struct key_hash : public unary_function<key, size_t >{
        size_t operator()(const key &k) const{
            return get<0>(k) * 100 + get<1>(k);
        }
    };

    unordered_map<key, int, key_hash> help;

    int minDistance(string word1, string word2) {
        return dp(word1, word2, word1.size()-1, word2.size()-1);
    }

    int dp(string word1, string word2, int i, int j){
        auto i_j = make_tuple(i, j);
        if(help.count(i_j) > 0) return help[i_j];

        if(i == -1) return j+1;
        if(j == -1) return i+1;

        if(word1[i] == word2[j]){
            help[i_j] = dp(word1, word2, i-1, j-1);
        }else{
            // 替换, 删除， 插入
            help[i_j] = m_min(
                dp(word1, word2, i-1, j-1) + 1, 
                dp(word1, word2, i-1, j) + 1,   
                dp(word1, word2, i, j-1) + 1  
            );
        }

        return help[i_j];
    }

    int m_min(int a, int b, int c){
        return min(a, min(b, c));
    }
};

// 动态规划
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));
        for(int i = 0; i <= m; ++i) dp[i][0] = i;
        for(int j = 0; j <= n; ++j) dp[0][j] = j;

        for(int i = 1; i <= m; ++i){
            for(int j = 1; j <= n; ++j){
                if(word1[i-1] == word2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = m_min(
                        dp[i - 1][j] + 1,
                        dp[i][j - 1] + 1,
                        dp[i-1][j-1] + 1
                    );
                }
            }
        }

        return dp[m][n];
    }

    int m_min(int a, int b, int c){
        return min(a, min(b, c));
    }
};