这个题目我上课学过了等以后有心情再写吧，就是很典型的动态规划算法而已。这个算法的时间复杂度是O（NM），空间复杂度是O（NM）。其中M，N分别为两个词的长度。
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
lw1, lw2 = len(word1), len(word2)
m = [[0] * (lw1+1) for _ in range(lw2+1)]
for i in range(lw1+1):
m[0][i] = i
for i in range(lw2+1):
m[i][0] = i
for i in range(1, lw2+1):
for j in range(1, lw1+1):
top = m[i-1][j] + 1
left = m[i][j-1] + 1
top_left = m[i-1][j-1]
if word1[j-1] != word2[i-1]:
top_left += 1
m[i][j] = min(top, left, top_left)
return m[lw2][lw1]PREVIOUSlc426.将二叉搜索树转化为排序的双向列表
NEXTjz037.序列化二叉树