题目描述

给定两个单词 word1 和 word2 ，请问最少需要进行多少次操作可以将 word1 变成 word2 。

你可以进行三种操作：

1. 插入一个字符；
2. 删除一个字符；
3. 修改一个字符；

样例1

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

样例2

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

算法

(动态规划) $O(n^2)$

经典的编辑距离问题。

状态表示：$f[i, j]$ 表示将 word1 的前 $i$ 个字符变成 word2 的前 $j$ 个字符，最少需要进行多少次操作。
状态转移，一共有四种情况（假定word的下标从1开始）：

1. 将 $word1[i]$ 删除或在 $word2[j]$ 后面添加 $word1[i]$，则其操作次数等于 $f[i-1, j] + 1$；
2. 将 $word2[j]$ 删除或在 $word1[i]$ 后面添加 $word2[j]$，则其操作次数等于 $f[i, j-1] + 1$；
3. 如果 $word1[i] = word2[j]$，则其操作次数等于 $f[i-1, j-1]$；
4. 如果 $word1[i] \neq word2[j]$，则其操作次数等于 $f[i-1, j-1] + 1$；

时间复杂度分析：状态数 $O(n^2)$，状态转移复杂度是 $O(1)$，所以总时间复杂度是 $O(n^2)$。

C++ 代码

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        if (!n || !m) return n + m;
        vector<vector<int>>f = 
            vector<vector<int>>(n + 1, 
            vector<int>(m + 1));
        f[0][0] = 0;
        for (int i = 1; i <= n; i ++ ) f[i][0] = i;
        for (int j = 1; j <= m; j ++ ) f[0][j] = j;
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
            {
                f[i][j] = f[i - 1][j - 1] + 
                    (word1[i - 1] != word2[j - 1]);
                f[i][j] = min(f[i][j], f[i - 1][j] + 1);
                f[i][j] = min(f[i][j], f[i][j - 1] + 1);
            }
        return f[n][m];
    }
};