题目
求两个词的编辑距离，可以进行 插入，删除，替换三种操作。
思路
动态规划 状态定义： dp[i][j]表示从word1[0:i-1]变换到word2[0:j-1]的最小编辑距离 状态初始化：第一行和第一列都好解释，因为两个字符串都可以删除至空值“”，然后相等 状态转移： 注意，更新dp[i][j]时，判断的是word1[i-1] 和 word2[j-1]
代码
class Solution:
def minDistance(self
, word1
: str, word2
: str) -> int:
n
= len(word1
)
m
= len(word2
)
dp
= [[0 for _
in range(m
+1)] for _
in range(n
+1)]
for i
in range(n
+1):
dp
[i
][0] = i
for j
in range(m
+1):
dp
[0][j
] = j
for i
in range(1,n
+1):
for j
in range(1,m
+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
], dp
[i
][j
-1], dp
[i
-1][j
-1]) + 1
return dp
[n
][m
]
