给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
1. 插入一个字符
2. 删除一个字符
3. 替换一个字符
示例 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')
链接（中文版）：https://leetcode-cn.com/problems/edit-distance
链接（英文版）：https://leetcode.com/problems/edit-distance
编辑距离是相互的，即a到aa的编辑距离和aa到a的编辑距离相同，都是1。a到aa是通过插入操作，反之是通过删除操作。
当我们求两个字符串的编辑距离时，分两种情况。
例如求aaas和bbs的编辑距离，两个字符串最后的字符都是s，则这两个字符串的编辑距离等于把最后的s都去掉，即aaa和bb的编辑距离，因为aaa和bb都加上了一个相同的字符s，编辑距离不变。
例如求aaas和bbk的编辑距离，最后的字符s和k不同，此时有三条路可以求取答案，我们选择最小的即可。
第一条路：用aaa和bbk的编辑距离加1，加1是因为aaa后边还有一个s，需要多一步插入或者删除操作。
第二条路：用aaas和bb的编辑距离加1，加1是因为bb后边还有一个k，需要多一步插入或者删除操作。
第三条路：用aaa和bb的编辑距离加1，加1是因为aaa后边的s和bb后边的k不同，需要多一步替换操作。
显然上述所有蓝色的编辑距离，都是问题的子集，我们用矩阵存储全部子集的答案，矩阵最右下角就是最终答案。如下图E1表示aaa和bb的编辑距离；E2表示aaa和bbk的编辑距离；E3表示aaas和bb的编辑距离。
| b | b | k | |
| a | |||
| a | |||
| a | E1 | E2 | |
| s | E3 |
求horse和ros的编辑距离。
为方便判断边界，我们先求出矩阵M第0行和第0列的内容。其中M[0][0]表示h和r的编辑距离，显然是1；
M[0][1]表示h和ro的编辑距离，由于h和o不同，则编辑距离就是h和r的编辑距离加1，等于2；
M[0][2]表示h和ros的编辑距离，由于h和s不同，则编辑距离就是h和ro的编辑距离加1，等于3；
M[1][0]表示ho和r的编辑距离，由于o和r不同，则编辑距离就是h和r的编辑距离加1，等于2；
M[2][0]表示hor和r的编辑距离，由于r和r相同，则编辑距离就是ho和空串的编辑距离，也就是ho的长度，等于2；
M[3][0]表示hors和r的编辑距离，由于s和r不同，则编辑距离就是hor和r的编辑距离加1，等于3；
M[4][0]表示horse和r的编辑距离，由于e和r不同，则编辑距离就是hors和r的编辑距离加1，等于4；
此时矩阵内容如下：
| r | o | s | |
| h | 1 | 2 | 3 |
| o | 2 | x1 | x2 |
| r | 2 | x3 | x4 |
| s | 3 | x5 | x6 |
| e | 4 | x7 | x8 |
然后按照上述讨论的情况一和情况二，按序求出x1到x8即可。
当求x1时，即M[1][1]，即ho到ro的距离，由于两个末尾字符都是o，属于情况一，所以M[1][1]=M[1-1][1-1]=M[0][0]=1。
当求x2时，即M[1][2]，即ho到ros的距离，由于两个末尾字符不同，属于情况二，所以M[1][2]=min(M[0][2], M[1][1], M[0][1])+1=M[1][1]+1=1+1=2。
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
len1, len2 = len(word1), len(word2)
if len1 == 0:
return len2
if len2 == 0:
return len1
M = [[0 for _ in range(len2)] for _ in range(len1)]
M[0][0] = 0 if word1[0] == word2[0] else 1
for y in range(1, len1):
M[y][0] = y if word1[y] == word2[0] else M[y-1][0] + 1
for x in range(1, len2):
M[0][x] = x if word2[x] == word1[0] else M[0][x-1] + 1
for y in range(1, len1):
for x in range(1, len2):
if word1[y] == word2[x]:
M[y][x] = M[y-1][x-1]
else:
M[y][x] = min(M[y-1][x-1], M[y-1][x], M[y][x-1]) + 1
return M[-1][-1]提交结果：
关键在于找出递推关系。