题目内容

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

提示

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

题解

本题考察动态规划。

首先，定义状态转移方程：F(i,j)，表示从word1的前i个字符，变成word2的前j个字符，最少需要进行的操作数量。

然后，我们要明确两点。第一点：最少操作的范围中一定不可能出现多余操作，即：先添加一个数删除一个数等类似多余操作；第二点：最少操作的顺序可以改变，即先修改某个字符再添加某个字符与先添加某个字符再修改某个字符效果等价。

基于以上分析，我们可以思考方案的“最后一步”操作的情况，形成递推关系式：

1、最后一步是删除A的最后一个字符后与B相同，意味着A[1,i - 1] == B [1, j], 因此：f[i, j] = f[i - 1, j] + 1;
2、最后一步是在A加上一个字符后与B相同，意味着A[1,i] == B[1, j - 1], 因此：f[i, j] = f[i, j - 1] + 1;
3、最后一步是将A的最后一个字符修改后与B相同，意味着A[1,i - 1] == B[1, j - 1], 因此：f[i,j] = f[i - 1, j - 1] + 1或 +0;（若最后一个字母一样就+0）

有了递推关系式，然后直接上代码即可。

代码

class Solution {
public:
    int minDistance(string a, string b) {
        int n = a.size(), m = b.size();//补一位，下标从1开始。
        a = ' ' + a, b = ' ' + b;
        vector<vector<int>> f(n + 1,vector<int>(m + 1)); 
        for(int i = 0; i <= n; i++)f[i][0] = i;
        for(int i = 1; i <= m; i++)f[0][i] = i;

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;
                int t = a[i] != b[j];//t用于判断是否是+1还是+0
                f[i][j] = min(f[i][j],f[i - 1][j - 1] + t);
            }
        }
        return f[n][m]; 
    }
};