```python class Solution: # 给你两个单词word1和word2，请返回将word1转换成word2所使用的最少操作数。 # 你可以对一个单词进行如下三种操作： # - 插入一个字符 # - 删除一个字符 # - 替换一个字符 # 0 <= word1.length, word2.length <= 500 # word1 和 word2 由小写英文字母组成 def minDistance(self, word1: str, word2: str) -> int: # 分析: # 每个元素位置都可能有四种情况: 不变、增、删、改 # 特殊处理!important: 将插入操作同化为删除操作; # 在word1中插入,就相当于在word2中删除 # 所以接下来就很容易处理了!! n1 = len( word1 ) n2 = len( word2 ) # 以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。 dp = [ [ 0 for _ in range( n2 + 1 ) ] for _ in range( n1 + 1 ) ] # 初始化 for i in range( n1 + 1 ): dp[ i ][ 0 ] = i # word1删除i次为"" for j in range( n2 + 1 ): dp[ 0 ][ j ] = j # word2删除j次为"" for i in range( 1, n1 + 1 ): for j in range( 1, n2 + 1 ): if word1[ i - 1 ] == word2[ j - 1 ]: dp[ i ][ j ] = dp[ i - 1 ][ j - 1 ] else: # 删除word1 / 删除word2 / 替换 dp[ i ][ j ] = min( dp[ i - 1 ][ j ], dp[ i ][ j - 1 ], dp[ i - 1 ][ j - 1 ] ) + 1 return dp[ n1 ][ n2 ] ```