【leetcode】72 Edit Distance

发表于 | 分类于 ，


描述

给定两个单词word1和word2，找到将word1转换为word2所需的最小操作数。

您对单词允许以下3个操作：

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

样例

样例1

1
2
输入: word1 = "horse", word2 = "ros"
输出: 3

样例2

1
2
输入: word1 = "intention", word2 = "execution"
输出: 5

思路

动态规划，dp[i][j] 代表长度为为 i word1 到长度为 j 的 words2 需要变换的最少次数。

当 words[i] == word2[j]: 显然 dp[i][j] = dp[i-1][j-1]

否则需要变换，

1
2
3
4
5
dp[i][j] = min(
    dp[i-1][j] + 1, 删除，因为已经到达了j，删除这个字符就可以了
    dp[i][j-1] + 1, 插入，一个元素，发现 j 还差一个元素（只到达了 j - 1，实际要到达 j ） ，因此插入一个元素
    dp[i-1][j-1] + 1 ,还有一个 i 元素和 一个 j 元素没有用到，替换成相等就可以了。
)

要好好理解一下，dp[i][j] = 1 代表 经过一次变换形成了 words2.substr(0,j) ，我们可以认为这个字符串就是当前的形成的状态。

真费劲。

代码

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

参考

原题链接