编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

示例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 由小写英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/edit-distance
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

编辑的含义

• 如果 word1[i] == word2[j]，那么比较 word1[0 .. i-1] 和 word2[0 .. j-1]。例如示例二因为两个单词最后的 “tion” 一样，就可以比较 “inten” 和 “execu”。
• 如果 word1[i] != word2[j]，可以做题目中给出的三个操作选项：
  • 执行插入操作，比较 word1[0 .. i] 和 word2[0 .. j-1]的结果；
  • 执行删除操作，比较 word1[0 .. i - 1] 和 word2[0 .. j]的结果；
  • 执行替换操作，比较 word1[0 .. i - 1] 和 word2[0 .. j - 1]的结果。

最终使得 两个词可以相等。选择三个选项中最小的那个加1（加1，即记录本次操作，将所有操作记录长度+1），获取当前可选操作中最快的方式。
模式识别
word1[0 .. i-1] 和 word2[0 .. j-1] 可以看作子问题，即可以使用自顶向下的递归和自底向上的动态规划。

自顶向下的递归

下面这种递归会超时，❌

function minDistance(word1: string, word2: string): number {
    const len1 = word1.length, len2 = word2.length;
    if (len1 === 0 || len2 === 0) return Math.max(len1, len2);
    if (word1.charAt(0) === word2.charAt(0)) {
        return minDistance(word1.substr(1, len1 -1), word2.substr(1, len2 - 1));  
    }
    const inserted = 1 + minDistance(word1, word2.substr(1, len2 - 1));
    const deleted = 1 + minDistance(word1.substr(1, len1 -1), word2);
    const replaced = 1 + minDistance(word1.substr(1, len1 -1), word2.substr(1, len2 - 1));
    return Math.min(inserted, deleted, replaced);
}

上述中一直使用到substr，字符串切片的时间复杂度为O(n)，所以可以改为下面方法，但同样超时，❌

function minDistance(word1: string, word2: string): number {
    const len1 = word1.length, len2 = word2.length;
    function helper(i: number, j: number): number {
        if (i === len1 || j === len2) return len1 - i + len2 -j;
        if (word1.charAt(i) === word2.charAt(j)) {
            return helper(i+1, j+1);  
        } else {
            const inserted = helper(i, j+1);
            const deleted = helper(i+1, j);
            const replaced = helper(i+1, j+1);
            return 1 + Math.min(inserted, deleted, replaced);
        }
    }
    return helper(0, 0);
}

自底向上的动态规划

可以参考题解中 Lucien 大佬的解题思路：https://leetcode.cn/problems/edit-distance/solution/bian-ji-ju-chi-by-leetcode-solution/

二维数组

dp[i][j] 代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数。
当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]；
当 word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
其中，dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作。
注意边界，针对第一行，第一列要单独考虑，我们引入 ‘’ 下图所示：

第一行，是 word1 为空变成 word2 最少步数，就是插入操作；
第一列，是 word2 为空，需要的最少步数，就是删除操作。

重要的是找出状态转移：根据字符是否相等和增删改的特性，通过保存操作数以及背后状态的意义，计算当前状态的值
1. 增，dp[i][j] = dp[i][j - 1] + 1
2. 删，dp[i][j] = dp[i - 1][j] + 1
3. 改，dp[i][j] = dp[i - 1][j - 1] + 1
这里可以查看 lkaruga 大佬的 图解：
https://leetcode.cn/problems/edit-distance/solution/edit-distance-by-ikaruga/

function minDistance(word1: string, word2: string): number {
    const n = word1.length, m = word2.length;
    if (n === 0 || m === 0) return Math.max(n, m);
    const dp: Array<Array<number>> = new Array(n + 1).fill(0).map(item => new Array(m + 1).fill(0));
    // 第一行
    for (let j = 1; j <= m; j++) dp[0][j] = dp[0][j - 1] + 1;
    // 第一列
    for (let i = 1; i <= n; i++) dp[i][0] = dp[i - 1][0] + 1;

    for (let i = 1; i <= n; i++) {
      for (let j = 1; j <= m; j++) {
        if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
            dp[i][j] = dp[i - 1][j - 1];  
        } else {
            dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;  
        }
      }
    }
    return dp[n][m];
}

时间复杂度：O(mn)
空间复杂度：O(mn)

一维数组 + 变量

注意：
上面dp[i][j]只和dp[i-1][j],dp[i][j-1],dp[i-1][j-1]三个量有关，即二维数组中，当前元素的左边，上边，左上角三个元素。可以拍平成一维数组，反复覆盖里面的值，则d[j] 对应d[i][j]，所以 d[i-1][j] 对应 d[j - 1]、d[i][j-1] 对应 d[j]，右上角d[i-1][j-1]使用变量单独存储：

function minDistance(word1: string, word2: string): number {
    const m = word1.length, n = word2.length;
    if (n === 0 || m === 0) return Math.max(n, m);
    const dp: Array<number> = new Array(n + 1).fill(0);
    for(let i=0; i<m+1; i++){
        let lu = dp[0];   // 初始化左上角变量，记录一维数组每一个位置更新前的值，即记录dp[i-1][j-1]
        dp[0] = i;  // 一维数组，dp[j]对应dp[i][j]，因此当j=0时，对应边界条件dp[i][0]=i
        for(let j=1; j<n+1; j++){
            if(i==0){
                dp[j] = j;  // 一维数组，dp[j]对应dp[i][j]，因此当i=0时，对应边界条件dp[0][j]=j
                continue;
            }
            const temp = dp[j];   // 临时变量记录更新前的值
            //更新j
            if(word1.charAt(i-1) == word2.charAt(j-1)){
                dp[j] = Math.min(dp[j-1] + 1, Math.min(dp[j] + 1, lu));
            }else{
                dp[j] = 1 + Math.min(dp[j-1], Math.min(dp[j], lu));
            }
            lu = temp; // 更新lu为j更新前的值，那么在下一次循环的时候，j变成j+，lu的值就为[i-1][j-1]
        }
    }
    return dp[n];
}

时间复杂度：O(mn)
空间复杂度：O(n)