编辑距离

发表于 分类于 ， 阅读次数： Waline： 本文字数： 2.1k 阅读时长 ≈ 2 分钟

72. 编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

示例：

输入：word1 = "horse", word2 = "ros"

输出：3

解释：

horse -> rorse (将 'h' 替换为 'r')

rorse -> rose (删除 'r')

rose -> ros (删除 'e')

思路：

if s1[i] == s2[j]:

  • 什么也不做
  • i, j同时向前移动

else:

​ 三选一：

  • 插入（inser）

  • 删除（delete）

  • 替换（replace）

dp(i,j)定义：返回s1[0...i] 和 s2[0...j] 的最小编辑距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        return dp(word1, word2, m - 1, n - 1);
    }
    int dp(string& s1, string & s2, int i, int j){
        //base case
        if(i == -1) return j + 1;
        if(j == -1) return i + 1;
        //s1[i] == s2[j]什么都不做，i,j同时向前移
        if(s1[i] == s2[j]){
            return dp(s1, s2, i - 1, j - 1);
        }else{
            //插入，删除，替换三选一
            return min(dp(s1, s2, i, j - 1) + 1, //插入
            min(dp(s1, s2, i - 1, j) + 1,        //删除
                dp(s1, s2, i - 1, j - 1) + 1));  //替换
        }
    }
};

有大量的重叠子问题，我们采用迭代的方法来解决

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
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));
        //base case, 某一个为空时
        for(int i = 1; i <= m; i++){
            dp[i][0] = i;
        }
        for(int j = 1; 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] = min(
                        dp[i][j - 1] + 1,
                        min(
                            dp[i - 1][j] + 1,
                            dp[i - 1][j - 1] + 1
                        )
                    );
                }
            }
        }
        return dp[m][n];
    }
};