错误的分析


编辑距离 - 图1
编辑距离 - 图2

递归解法

  1. class Solution:
  2.     def minDistance(self, word1: str, word2: str) -> int:
  3.         def dp(i, j):
  4.             """
  5.             dp(i, j): word_i, word_j的最短编辑距离
  7.             假设：
  8.             word:x_1...x_n         y_1...y_m
  9.             编辑结果：z_1...z_k
  10.             显然z_必然然属于set(x) | set(y), 即z中的元素要么属于x, 要么属于y(或者两者共有)
  12.             若x_n == y_m, 显然。
  13.             若x_n != ym， 假设z_k == x_n, 那么y中 经过增 删 替换后必要有 y_ == z_k:
  14.                 替换: 1 + dp(i-1, j-1)     将y_m替换成x_n
  15.                 增加： 1 + dp(i-1, j)      增加y_(尾部), 使得y_= x_n
  16.                 删除： 1 + dp(i, j-1)      删除y_m
  18.             反之亦然。
  19.             """
  20.             # base case
  21.             if i < 0:
  22.                 return j + 1
  23.             if j < 0:
  24.                 return i + 1
  25.             # make progress
  26.             if word1[i] == word2[j]:
  27.                 return dp(i - 1, j - 1)
  28.             else:
  29.                 return 1 + min(
  30.                     dp(i, j - 1),
  31.                     dp(i - 1, j),
  32.                     dp(i - 1, j - 1)
  33.                 )
  35.         return dp(len(word1) - 1, len(word2) - 1)

正确的分析