LC 72编辑距离Edit Distance　中等

每次可插入、删除或替换一个字符，求把 word1 变成 word2 的最少操作次数。

思路 经典编辑距离：相等取左上，否则 min(左上替换, 上删除, 左插入) + 1，边界为空串长度。时间 O(mn)。

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        f = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1):
            f[i][0] = i
        for j in range(1, n + 1):
            f[0][j] = j
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    f[i][j] = f[i - 1][j - 1]
                else:
                    f[i][j] = 1 + min(f[i - 1][j],
                                      f[i][j - 1],
                                      f[i - 1][j - 1])
        return f[m][n]