编辑距离

难度： 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（芜湖！

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