72.编辑距离——hard

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/edit-distance

思路：
定义dp[i][j] 为 word1[0,……,i-1] ->word2[0,……,j-1]的编辑次数，
插入一个字符到word1 ：dp[i-1][j] +1
删除一个字符,可以看做是对word2插入一个字符 : dp[i][j-1] +1
修改一个字符：dp[i-1][j-1]+1，如果word[i-1] === word[j-1]，此时不需要更改，则为dp[i-1][j-1]
dp[i][j] 取三种操作中的最小值。
因为编辑距离随着字符串的增长，是单调递增的。所以，要求最终的最小值，必须要保证对于每个子串，都取得了最小值。有了这点，就可以使用迭代的方式，一步步推导下去，直到两个字符串结束比较。
复杂度分析：
时间复杂度O(nm) n , m 分别为 word1 ， word2 长度
空间复杂度O(nm)

var minDistance = function (word1, word2) {
    let length1 = word1.length;
    let length2 = word2.length;
    let dp = new Array(length1 + 1).fill(undefined).map(() => new Array(length2 + 1).fill(0));
    for (let i = 0; i < length1 + 1; i++) {
        dp[i][0] = i;
    }
    for (let j = 0; j < length2 + 1; j++) {
        dp[0][j] = j;
    }
    for (let i = 1; i < length1 + 1; i++) {
        for (let j = 1; j < length2 + 1; j++) {
            let left = dp[i][j - 1] + 1;
            let left_top = dp[i - 1][j - 1];
            let top = dp[i - 1][j] + 1;
            if (word1.charAt(i - 1) !== word2.charAt(j - 1))
                left_top += 1;
            dp[i][j] = Math.min(left, Math.min(left_top, top));
        }
    }
    return dp[length1][length2];
};