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

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

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

提示：
word1, word2范围：[0, 500]

题解

设r[i][j]是word1前i个字符转换成word2前j个字符所需的最少操作数

  • 当i == 0 or j == 0：那么操作只会是插入（i == 0）或删除（j == 0），那么r[0][j] = j，r[i][0] = i。

  • 当r != 0 and j != 0时，所对应的三种操作：

    • 插入：r[i][j] = r[i][j-1] + 1
    • 删除：r[i][j] = r[i-1][j] + 1

    • 替换：r[i][j] = r[i-1][j-1] + 1

      1. class Solution:
      2. def minDistance(self, word1: str, word2: str) -> int:
      3.    m, n = len(word1), len(word2)
      4.    r = [[0] * (n+1) for i in range(m+1)]
      5.    for i in range(m+1):
      6.        r[i][0] = i
      7.    for j in range(n+1):
      8.        r[0][j] = j
      10.    for i in range(1, m+1):
      11.        for j in range(1, n+1):
      12.            r[i][j] = min(r[i-1][j], r[i][j-1], r[i-1][j-1]) + 1
      13.            # 当前字符相等，只需改动前面i-1个字符
      14.            if word1[i-1] == word2[j-1]:
      15.                r[i][j] = min(r[i][j], r[i-1][j-1])
      16.    return r[m][n]