题目链接：https://leetcode.cn/problems/edit-distance/
难度：困难

描述：
给你两个单词 word1 和 word2， 请返回将 _word1_ 转换成 _word2_ 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

提示：
长度：[0, 500]

题解

  1. class Solution:
  2.     def minDistance(self, word1: str, word2: str) -> int:
  3.         # r[i][j]: word1[:i] -> word2[:j]的最少操作数
  4.         # insert:  r[i][j] = r[i][j-1] + 1
  5.         # delete:  r[i][j] = r[i-1][j] + 1
  6.         # replace: r[i][j] = r[i-1][j-1] + 1
  8.         m, n = len(word1), len(word2)
  9.         r = [[0] * (n+1) for _ in range(m+1)]
  11.         # "" -> "" = 0
  12.         # "" -> word2[:j] = j
  13.         # word1[:i] -> "" = i
  15.         for j in range(1, n+1):
  16.             r[0][j] = j
  18.         for i in range(1, m+1):
  19.             r[i][0] = i
  22.         for i in range(1, m+1):
  23.             for j in range(1, n+1):
  24.                 r[i][j] = min(r[i][j-1], r[i-1][j], r[i-1][j-1]) + 1
  25.                 if word1[i-1] == word2[j-1]:
  26.                     r[i][j] = min(r[i-1][j-1], r[i][j])
  28.         return r[-1][-1]