题目描述

给你两个单词 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')

算法

(DP) $O(mn)$

典型的字符串状态转换问题，注意题目的关键字“最小”、 word1转换成 word2三种方法
同时关键的一点是状态转换和顺序没有关系， 比如“abc”转换成 "c",
可以先删掉 a，再删掉 b得到 c
也可以先删掉 b， 再删掉 a得到 c
定义：f[i, j]: 所有 word1 前[1-i]个字符转换成word2前[1-j]所有方案的集合，所有集合的最小值
那么： f[i,j]由题意可知，word2 [1,j]可以由 word1 [1,i]通过添加一个字符／删除一个字符／修改一个字符三种方式转换而来
1. word1 [1,i] 添加一个字符 word1[i+1] 得到 word2 [1, j], 则 f[i, j] = f[i, j-1] + 1
2. word1 [1,i] 删除一个字符 word1[i] 得到 word2 [1,j], 则 f[i, j] = f[i-1, j] + 1
3. word1 [1,i] 修改一个字符 word1[i] 得到 word2 [1,j], 则 f[i,j] = f[i-1, j-1] + 1/0(word1[i]是否等于word[j])
综合上面三种情况，
状态转移方程： f[i,j] = min(min(f[i,j-1], f[i-1, j]) + 1, f[i-1,j-1] + 1/0)

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    int minDistance(string word1, string word2) {
        if(word1.size() == 0 || word2.size() == 0){
            return max(word1.size(), word2.size());
        }

        int m = word1.size(), n = word2.size();
        word1 = ' ' + word1;
        word2 = ' ' + word2;

        vector<vector<int>> f(m + 1, vector<int>(n + 1));
        for(int j = 0; j <= n; j++) f[0][j] = j;
        for(int i = 0; i <= m; i++) f[i][0] = i;

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                f[i][j] = min(f[i][j-1], f[i-1][j]) + 1;
                int t = 0;
                if(word1[i] != word2[j]){
                    t = 1;
                }
                f[i][j] = min(f[i][j], f[i-1][j-1] + t);
            }
        }

        return f[m][n];
    }
};