BM75　编辑距离(一)¶

较难通过率 44.53%python3核心代码模式样例通过牛客 AC字符串动态规划

牛客原题　源码

讲解章节：线性 DP

一句话

插入/删除/替换三选一取最小，再把二维表滚动压成一行。

解题思路¶

这题考什么¶

双序列 DP 的标准形态：状态用两个前缀长度描述，转移按「两串的末尾字符怎么对齐」分类，见线性 DP。

状态定义：dp[i][j] = 把 str1 的前 i 个字符变成 str2 的前 j 个字符的最少操作数。边界（一方为空时只能一直插或一直删）：

dp[0][j] = j        往空串里插 j 个字符
dp[i][0] = i        把 i 个字符逐个删光

转移方程，记 a = str1[i-1]、b = str2[j-1]：

a == b:  dp[i][j] = dp[i-1][j-1]                    末尾天然对齐，不花操作
a != b:  dp[i][j] = 1 + min(dp[i-1][j-1],           把 a 替换成 b
                            dp[i-1][j],             删掉 a
                            dp[i][j-1])             在 str1 末尾插入 b

三个候选恰好对应题面允许的三种操作，且都把问题缩小一格，无后效性成立。答案是 dp[m][n]。

每一行只依赖上一行的同列与左上角，以及本行的左邻，所以行这一维可以滚掉，只留长度 n+1 的一维数组：扫到第 j 列时 dp[j] 尚未覆盖（正是「上」），dp[j-1] 已覆盖（正是「左」），而「左上角」在 dp[j] 被覆盖的瞬间就丢了——所以要用临时变量 diag 在覆盖之前把它接住，每列末尾再把本列的「上」交棒给下一列的「左上」。这是滚动数组里最典型的一处陷阱，见 DP 入门。

数据规模与复杂度¶

两串长度均 <= 1000，只含小写字母，时限 2 秒（其他语言）。时间 O(m*n) 最坏 1e6 次内层迭代，判题机比本机慢数倍，所以内层刻意压到最少操作：三路取最小用手写比较而不是 min()，每轮先把 str1[i-1] 存进局部变量 a，避免每格重复寻址。空间 O(min(m, n))：把较短的串放在内层维度上，滚动数组最长也只有 1001 项。

坑在哪¶

diag 的维护顺序不能颠倒：进入内层前 diag = dp[0]（旧的 dp[i-1][0]），然后才把 dp[0] 改写成 i。先写 dp[0] = i 会让第一列的左上角变成本行的值，整行错。
每列结束时 diag = up（本列的「上」），因为下一列的「左上」正是本列的「上」。漏掉这一步，diag 会一直停在行首，后面所有替换操作都基于错误的对角值。
交换两串是安全的：插入与删除互为逆操作、替换与自身互逆，所以编辑距离是对称的，d(str1, str2) == d(str2, str1)。交换只为让滚动数组取到 min(m, n) 的长度，不影响答案。
n == 0 时答案就是 m（把 str1 删光），要在建表前挡掉—— 否则 dp 只有 dp[0] 一项，内层循环不进，返回的是 dp[0] 而不是 m。
字符相同时是直接继承 dp[i-1][j-1]，不是 dp[i-1][j-1] + 0 之外还要与另外两项取最小。写成一律取三者最小再加判断，会在等值时凭空多算操作。

样例复核¶

"nowcoder" 与 "new"：交换后内层维度是长度 3 的 "new"，最终 dp[3] = 6，对应「替换 o 为 e、删掉 coder 的 5 个字符」，与期望输出一致。

参考实现¶

solutions/nowcoder/BM75/sol.py
from typing import List, Optional


class Solution:
    def editDistance(self, str1: str, str2: str) -> int:
        # 编辑距离是对称的（插入与删除互逆），交换不改变答案；
        # 让 str2 成为较短的一方，滚动数组的长度就压到 min(m, n)
        if len(str2) > len(str1):
            str1, str2 = str2, str1
        m, n = len(str1), len(str2)
        if n == 0:
            return m                    # 目标是空串，只能把 str1 逐个删光

        # dp 只留一行，省掉的是**行**这一维。此刻 dp[j] 的含义是 dp[i-1][j]（上一行）。
        # 初值 dp[j] = j 就是边界 dp[0][j] = j：往空串里插 j 个字符
        dp = list(range(n + 1))
        for i in range(1, m + 1):
            diag = dp[0]        # 先接住旧的 dp[i-1][0]，它是本行第一格的左上角
            dp[0] = i           # 再改写成本行边界 dp[i][0] = i；顺序颠倒就整行错
            a = str1[i - 1]     # 本轮固定的字符，提出来省掉内层的重复寻址
            for j in range(1, n + 1):
                up = dp[j]      # dp[j] 尚未覆盖，此刻仍是上一行的 dp[i-1][j]，即「上」
                if a == str2[j - 1]:
                    dp[j] = diag            # 末尾对齐，直接继承左上角，不花操作
                else:
                    left = dp[j - 1]        # 本行已更新过的一格，即「左」
                    # 三路取最小：左上=替换、上=删除、左=插入；手写比较省掉 1e6 次 min() 调用
                    dp[j] = 1 + (diag if diag <= up and diag <= left
                                 else up if up <= left else left)
                diag = up       # 下一列的左上角，正是本列的正上方
        return dp[n]

BM75 编辑距离(一)¶