【LeetCode】72. Edit Distance

Posted on | Edited on

Problem Link

概览

编辑距离问题是经典的实用问题。给定一个字符串，定义在该字符串的三种操作：

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

那么两个字符串A和B的编辑距离定义为通过上述三种操作将A编辑成B的最少操作数。

问题给定两个字符串，求其之间的编辑距离。

动态规划

编辑距离问题也是一个经典的动态规划问题，直观上很难求解的两个字符串的编辑距离通过状态转移就能轻易解出。

定义状态：

DP[i][j]表示A的长度为i的前缀到B的长度为j的前缀的编辑距离；那么答案为DP[|A|][|B|]。

定义状态转移方程：

DP[i][j]可以通过DP[i-1][j]，DP[i][j-1]以及DP[i-1][j-1]求得，具体来说：

  • 当A[i-1]与B[j-1]相等时，DP[i][j] = DP[i-1][j-1]。
  • 当A[i-1]与B[j-1]不等时，考虑下面三种情况的最小值：
    • DP[i-1][j] + 1，由A的前i-1个字符变为B的前j个字符并删除A[i]；
    • DP[i][j-1] + 1，由A的前i个字符变为B的前j-1个字符并新增B[j]；
    • DP[i-1][j-1] + 1，由A的前i-1个字符变为B的前j-1个字符并替换A[i]。

综上，可得状态转移方程如下：

1
2
3
4
DP[0][j] = j for all j in 0, 1, ..., |B|
DP[i][0] = i for all i in 0, 1, ..., |A|
DP[i][j] = DP[i - 1][j - 1] if A[i - 1] == B[j - 1]
DP[i][j] = min{DP[i - 1][j], DP[i][j - 1], DP[i - 1][j - 1]} + 1 if A[i - 1] != B[j - 1]

时间复杂度：$O(|A||B|)$
空间复杂度：$O(|A||B|)$

附录

我的解答