pythonTip 99 编辑距离

题目描述： 设 A 和 B 是 2 个字符串。要用最少的字符操作将字符串 A 转换为字符串 B。 这里所说的字符操作包括 (1)删除一个字符； (2)插入一个字符； (3)将一个字符改为另一个字符。 将字符串 A 变换为字符串 B 所用的最少字符操作数称为字符串 A 到 B 的编辑距离，记为d(A，B)。 试设计一个有效算法，对任给的 2 个字符串 A 和 B，计算出它们的编辑距离 d(A，B)。 如： A=”fxpimu” B=”xwrs” 则输出5.

示例： 输入： A = “fxpimu” B = “xwrs” 输出： 5

分析:

我们需要将 字符串A（源串） 转换成 字符串B（目标串），只有 3 种操作（见题目）。

我最初的想法。

假设： A = “fxpimu” ，B = “xwrs”， 为了减少字符串的操作次数，有直观的想法： 保留相同字符，修改其他的字符。

但是这样我们还需要考虑字符之间的顺序，例如： A=”abc”， B = “bdeaggc” ； A = “abc”， B=”adebggc”， 这两组字符串相同字符都是 “abc”， 但是需要修改的次数就不一样。而如何寻找字符之间的顺序呢？ 机智的我，没有想出来。

我们定义一个数组 nums[i， j] = a， 表示 源串前 i 个 和 目标串前 j 个 相匹配 需要 a步。

存在2种情况：

1. 其中一个串为空。如果 i = 0，则 nums[i，j] = j；如果 j = 0，则 nums[i，j] = i。即 nums[0，j] = j； nums[i， 0] = i。 例如，A=”“， B = “abc” 需要 3 步。 A=”abcd”， B = “” 需要 4 步。
2. 两个串都不为空。nums[i， j] 和 {nums[i-1，j]， nums[i， j-1]， nums[i-1， j-1]} 有关。为什么不和 nums[i-3， j] 有关呢？ 因为nums[i-3， j] 可以依次由 nums[(((i-1)-1)-1)， j] 推导而来。

对于第2种情况， nums[i， j] 可由 nums[i-1， j] 插入字符， nums[i，j-1] 删除字符 ， nums[i-1，j-1] 修改字符 得来。

插入 和 删除容易理解，因为这两种方法是肯定需要一次操作的。 但是修改不一样，如果 源串的第 i 个字符 和 目标串 第 j 个字符相等，就不需要 操作一次，否则 则需要一次操作。

所以算法流程为：

1. 将 nums[i，0] 置为 i，将 nums[0，j] 置为 j。

2. 将源串作为行，目标串作为列，开始遍历。

   1. nums[i，j] = min(nums[i-1， j]，nums[i，j-1]) + 1

   2. 判断 源串的第 i 个字符 和 目标串 第 j 个字符是否相等。

      1. 相等： nums[i，j] = min(nums[i， j]， nums[i-1，j-1])
      2. 不相等： nums[i，j] = min(nums[i，j]， nums[i-1，j-1] + 1)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

len_a = len(A) + 1
len_b = len(B) + 1

nums = [[0 for i in range(len_b)] for j in range(len_a)]

for i in range(len_a):
    nums[i][0] = i

for i in range(len_b):
    nums[0][i] = i

for i in range(1, len_a):
    for j in range(1, len_b):
        nums[i][j] = min(nums[i-1][j]+1, nums[i][j-1] + 1)
        if A[i-1] == B[j-1]:
            nums[i][j] = min(nums[i][j], nums[i-1][j-1])
        else:
            nums[i][j] = min(nums[i][j], nums[i-1][j-1] + 1)
# 最后 为什么要  -1?  因为字符串起始下标为 0。 len_a - 1 就是对应的最后一个字符。
print(nums[len_a-1][len_b-1])