72. 编辑距离

https://leetcode-cn.com/problems/edit-distance/

解法一：dp

主要想法就是已知word1[0…i-2]转换到word2[0…j-2]的距离，在此基础上看最后一位需要何种编辑，求word1[0…i-1]转换到word2[0…j-1]的距离。

用dp[i][j]表示word1[0...i-1]转换到word2[0...j-1]的距离，（为何要退一位表示？因为i或j为0表示空串）。初始：dp[0][0] = 0（空串到空串不需要操作），dp[i][0] = i（变成空串只能删除操作），dp[0][j] = j（空串只能插入操作）

主要分两种情况讨论：

若word1[i-1] == word2[j-1]，即i-1位置不用编辑，则dp[i][j]=dp[i-1][j-1]；

若word1[i-1] != word2[j-1]，又分三种情况：

1.若两串退一位后相等，即word1[0...i-2] == word2[0...j-2]，将word1[i-1]替换为word2[j-1]即可，多出一次操作，即dp[i][j]=dp[i-1][j-1]+1

2.若串1退一位后相等，即word1[0...i-2] == word2[0...j-1]，将word1[i-1]删除即可，也是一次操作：dp[i][j]=dp[i-1][j]+1

3.若串2退一位后相等，即word1[0...i-1] == word2[0...j-2]，将word2[j-1]插入串1末尾即可，也是一次操作：dp[i][j]=dp[i][j-1]+1

综上，当word1[i-1] != word2[j-1]时，dp[i][j]取上面三种情况的最小值

class Solution:
    def minDistance(self, word1: 'str', word2: 'str') -> 'int':
        m, n = len(word1), len(word2)
        dp = [[0] * (n+1) for _ in range(m+1)]
        #边界
        for i in range(1, m+1):
            dp[i][0] = i
        for j in range(1, n+1):
            dp[0][j] = j

        for i in range(1, m+1):
            for j in range(1, n+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1 
        return dp[m][n]

js：

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function(word1, word2) {
    let m = word1.length, n = word2.length
    const dp = new Array(m+1).fill(0).map(() => new Array(n+1).fill(0))
    for (let i = 1; i < m+1; i++) {
        dp[i][0] = i
    }
    for (let j = 1; j < n+1; j++) {
        dp[0][j] = j
    }
    for (let i = 1; i < m+1; i++) {
        for (let j = 1; j < n+1; j++) {
            if (word1[i-1] == word2[j-1]) {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
            }
        }
    }
    return dp[m][n]
};