LeetCode 72 编辑距离

发布于 2022-07-15  122 次阅读


编辑距离

难度: hard

题目内容

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

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

1. 插入一个字符
2. 删除一个字符
3. 替换一个字符

示例 1:

输入:word1 = "horse", word2 = "ros"
输出:3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2:

输入:word1 = "intention", word2 = "execution"
输出:5
解释:
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示:

0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成

题目提供代码

class Solution {
public:
    int minDistance(string word1, string word2) {

    }
};

思路

看到这道题目,第一反应是字符串匹配,尽可能匹配多的字符串,然后剩下的再处理,因为在同样的字符串匹配情况下,是否存在删除情况成了一个大问题,然后想了很久,发现了字符串匹配可以把B的删除改变为A的添加,这样的话就不用考虑删除的问题,但是这样就和优先匹配产生了矛盾,数据范围是500,本来想暴力试试的,但是还是觉得应该是DP,然后就开始递推:

若已知字符串A转换到B最少要N步
那么接下来,若B增加一个字符,就是N+1步。
这个时候出现了特例abcde->abcd:1步 abcde->abcde:0步
因为没有考虑A的删除,也就是B的增加,所以应该知道B转换到A的步数。
所以应该是min(A->B,B->A);
试了试样例还是不对,然后就想到了A+1->B+1的情况
然后想出了->min(A->B,B->A,A+1->B+1)的递推式;
样例测试还是不对  终于找到了最终bug 当A增加的字符和B一样时,最后步数不会加1;
最终递推式 min((A->B)+1,(B->A)+1,(A+1->B+1)(特判是否+1));

AC代码

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.length();
        int m = word2.length();
        // 有一个字符串为空串
        if (n * m == 0) return n + m;
        // DP 数组
        vector<vector<int>> D(n + 1, vector<int>(m + 1));
        // 边界状态初始化
        for (int i = 0; i < n + 1; i++) {
            D[i][0] = i;
        }
        for (int j = 0; j < m + 1; j++) {
            D[0][j] = j;
        }
        // 计算所有 DP 值
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                int left = D[i - 1][j] + 1;
                int down = D[i][j - 1] + 1;
                int left_down = D[i - 1][j - 1];
                if (word1[i - 1] != word2[j - 1]) left_down += 1;
                D[i][j] = min(left, min(down, left_down));

            }
        }
        return D[n][m];
    }
};

题目链接

完美AC(芜湖!

- 因为这是随笔博客,不是写题解,只是为了记录和督促自己学习,所以……


用代码改变世界