题目分析

编辑距离是一个非常经典的问题了，这是小伙伴们必须掌握的算法，这个题目在编辑距离的基础上加以修改，其思路并没有变换，先用20分钟动手尝试一下如何求解。

DP

用二维数组dp[i][j]表示a的前i个单词与b的前j个单词的编辑距离。

当a[i]与b[j]相同时
$$dp[i][j] = dp[i - 1][j - 1]$$
当a[i]与b[j]不相同时，又可以分成4种情况
- 当a[i]和b[j]都是s中的元素时
  $$dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j])$$
  其中第一项为a[i]与b[j]都跳过，第二项为跳过a[i]，第三项为跳过b[j]
- 当a[i]是s中的元素时
  $$dp[i][j] = min(dp[i - 1][j - 1] + 1, dp[i - 1][j], dp[i][j - 1] + 1)$$
  其中第一项为将a[i]替换为b[j]，第二项为跳过a[i]，第三项为删除b[j]
- 当b[j]是s中的元素时
  $$dp[i][j] = min(dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1, dp[i][j])$$
  其中第一项为将a[i]替换为b[j]，第二项为删除a[i]，第三项为跳过b[j]
- 当a[i]和b[j]都不是s中的元素时
  $$dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1$$
  其中第一项为将a[i]替换为b[j]，第二项为删除a[i]，第三项为删除b[j]

状态转移方程较为复杂，小伙伴们好好理解。算法的**时间复杂度为$O(mn)$，空间复杂度为$O(mn)$**。

import sys


for line in sys.stdin:
    stop_word = line.strip().split()
    a = sys.stdin.readline().strip().split()
    b = sys.stdin.readline().strip().split()
    lena, lenb = len(a), len(b)
    dp = [[0 for _ in range(lenb + 1)] for _ in range(lena + 1)]
    for i in range(1, lena + 1):
        dp[i][0] = dp[i - 1][0]
        dp[i][0] += 1 if a[i - 1] not in stop_word else 0
    for i in range(1, lenb + 1):
        dp[0][i] = dp[0][i - 1]
        dp[0][i] += 1 if b[i - 1] not in stop_word else 0
    for i in range(1, lena + 1):
        for j in range(1, lenb + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                if a[i - 1] in stop_word and b[j - 1] in stop_word:
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j])
                elif a[i - 1] in stop_word:
                    dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1] + 1, dp[i][j - 1] + 1)
                elif b[j - 1] in stop_word:
                    dp[i][j] = min(dp[i][j - 1], dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1)
                else:
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1
    print(dp[-1][-1])

优化DP

这个题目有趣的地方在于，我们可以将a和b中的所有出现在s中的字符都跳过，进行普通的编辑距离即可。
假设a[i]在s中，那么a[i]会被保留或者跳过，如果选择保留，那么一定和某个单词进行了匹配，则进行修改操作。那么等价于将其忽略，然后增加一个单词。
如A是s中的单词，字符串a为BAC，字符串b为BBC，此时a想变为b，可以将a中的A保留，并且进行修改，将A改成B，那么两个字符串相同，此时编辑距离为1，这个操作等价于将A忽略，然后插入一个单词B。
用公式进行说明，当a[i]是s中的元素时
$$dp[i][j] = min(dp[i - 1][j - 1] + 1, dp[i - 1][j], dp[i][j - 1] + 1)$$
其中第一项为将a[i]替换为b[j]，第二项为跳过a[i]，第三项为删除b[j]
第一项一定大于等于第二项，我们可以认为dp[i - 1][j - 1]在插入了一个b[j]单词，因此
$$dp[i - 1][j - 1] + 1 \ge dp[i - 1][j]$$
所以上面的式子可以转换为
$$dp[i][j] = min(dp[i - 1][j], dp[i][j - 1] + 1)$$
这个状态还可以继续简化
$$dp[i][0] = dp[i - 1][0] \ \ if \ \ j = 0$$
$$\begin{align} dp[i][1] & = min(dp[i - 1][1], dp[i][0] + 1) \ \ if \ \ j = 0 \ & = min(dp[i - 1][1], dp[i - 1][0] + 1)\ \end{align}$$
上面已经说明了
$$dp[i - 1][j - 1] + 1 \ge dp[i - 1][j]$$
$$dp[i][1] = dp[i - 1][1] \ \ if \ \ j = 0$$
利用数学归纳法可以轻易求得
$$dp[i][j] = dp[i - 1][j]$$
因此当a[i]出现在单词列表s中，可以将a[i]直接忽略，不会对结果产生影响。
算法的**时间复杂度为$O(mn)$，空间复杂度为$O(mn)$**。在很多单词出现在单词列表中，时间复杂度和空间复杂度比第一种算法低得多。

import sys


for line in sys.stdin:
    stop_word = line.strip().split()
    a = sys.stdin.readline().strip().split()
    b = sys.stdin.readline().strip().split()
    a = [x for x in a if x not in stop_word]
    b = [x for x in b if x not in stop_word]
    lena, lenb = len(a), len(b)
    dp = [[0 for _ in range(lenb + 1)] for _ in range(lena + 1)]
    for i in range(1, lena + 1):
        dp[i][0] = i
    for i in range(1, lenb + 1):
        dp[0][i] = i
    for i in range(1, lena + 1):
        for j in range(1, lenb + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1
    print(dp[-1][-1])

刷题总结

编辑距离的问题，小伙伴们一定要掌握它，肯定是通过动态规划来解决的，当题目变化时，我们的状态转移方程可能也会发生改动，一定要开动脑筋，思考如何去修改。