LC72　编辑距离¶

中等通过率 64.2%python3核心代码模式多维动态规划样例通过牛客 AC字符串动态规划

牛客原题　源码

讲解章节：线性 DP

一句话

插入、删除、替换三个来源取最小，二维表滚成一行并用临时变量接住左上角。

解题思路¶

这题考什么¶

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

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

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

转移方程，记 a = word1 的第 i 个字符、b = word2 的第 j 个字符：

a == b:  f[i][j] = f[i-1][j-1]
a != b:  f[i][j] = 1 + min(f[i-1][j-1], f[i-1][j], f[i][j-1])

三个来源逐一对应题面允许的三种操作，这是全题最该讲透的一点：

f[i-1][j-1] -> **替换**。两个末尾字符都被消费掉，一次操作把 a 改成 b，
               剩下的问题是「前 i-1 变成前 j-1」。
f[i-1][j]   -> **删除**。只消费 word1 的末尾字符，一次操作把 a 删掉，
               剩下的问题是「前 i-1 变成前 j」。
f[i][j-1]   -> **插入**。只消费 word2 的末尾字符，一次操作在 word1 末尾补上 b，
               剩下的问题是「前 i 变成前 j-1」。

三者穷尽了「最后一步动了什么」的全部可能，且都把问题严格缩小，无后效性成立。答案是 f[m][n]。

滚动成一行时的陷阱：每一格用到上一行的同列（「上」）、上一行的前一列（「左上」）与本行的前一列（「左」）。只留一维数组时，扫到第 j 列的瞬间：

dp[j] 尚未覆盖 -> 正是「上」
dp[j-1] 已覆盖 -> 正是「左」
「左上」呢？它是**上一列的 dp[j-1] 在被覆盖之前的旧值**，已经丢了。

所以必须用一个临时变量 diag 在覆盖发生之前把它接住：进入内层前 diag 取旧的 dp[0]，每列算完后把本列的「上」交棒给下一列的「左上」。这是滚动数组里最典型的一处坑，见 DP 入门。

数据规模与复杂度¶

0 <= word1.length, word2.length <= 500，均为小写英文字母。注意下界是 0，两串都可能是空串。时间 O(m * n) 最坏 500 * 500 = 2.5e5 次内层迭代，毫不吃力。空间 O(min(m, n))：把较短的串放到内层维度上，滚动数组最长只有 501 项。

朴素递归不记忆化时每层分三叉，深度 m+n，调用数是 3 的 1000 次方量级，完全不可行；DP 把重复子问题压成 2.5e5 个格子，每个只算一次。

坑在哪¶

diag 的维护顺序不能颠倒。进入内层前必须先 diag = dp[0]（此刻它还是旧的 f[i-1][0]，正是本行第一格的左上角），然后才把 dp[0] 改写成 i。先写 dp[0] = i 会让第一列的左上角变成本行的值，整行连锁出错。
每列结束时 diag = up（本列的「上」），因为下一列的「左上」正是本列的「上」。漏掉这一步，diag 会一直停在行首的旧值，之后所有替换分支都基于错误的对角值。
up 必须在 dp[j] 被覆盖之前取出。写成先赋值 dp[j] 再读 up，读到的是刚写进去的新值，整条递推塌掉。
字符相同时是直接继承 f[i-1][j-1]，而不是在三者取最小之后再加 0。写成一律 1 + min(...) 再打补丁，会在等值时凭空多算一次操作。
交换两串是安全的：插入与删除互为逆操作、替换与自身互逆，所以编辑距离对称，d(word1, word2) == d(word2, word1)。交换只为把滚动数组压到 min(m, n)，不影响答案。
n == 0（较短的一方是空串）必须在建表前挡掉。否则 dp 只有 dp[0] 一项，内层循环一次都不进，返回的是 dp[0] 而不是 m。由于前面已经交换过，此时 n == 0 意味着两串至少有一个是空的，答案就是较长者的长度。

样例复核¶

word1 = "horse"、word2 = "ros"。word1 本就更长，不触发交换，内层维度是长度 3 的 "ros"。

dp 初值 [0, 1, 2, 3]
i=1 (a='h')：diag=0, dp[0]=1；三格都不匹配 -> dp = [1, 1, 2, 3]
i=2 (a='o')：dp[0]=2；'o' 与 'r' 不匹配得 2，'o'=='o' 继承 diag=1 -> dp = [2, 2, 1, 2]
i=3 (a='r')：dp[0]=3；'r'=='r' 继承 diag=2 -> dp = [3, 2, 2, 2]
i=4 (a='s')：dp[0]=4；'s'=='s' 在第 3 列继承 diag=2 -> dp = [4, 3, 3, 2]
i=5 (a='e')：dp[0]=5 -> dp = [5, 4, 4, 3]

返回 dp[3] = 3，对应「h 换成 r、删掉 r、删掉 e」，与期望输出一致。

参考实现¶

solutions/leetcode/LC72/sol.py
from typing import List, Optional


class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        # 编辑距离是对称的（插入与删除互为逆操作），交换不改变答案，
        # 只为让内层维度取到较短的一方，滚动数组长度压到 min(m, n)
        if len(word2) > len(word1):
            word1, word2 = word2, word1
        m, n = len(word1), len(word2)
        # 交换之后 n == 0 意味着目标是空串，只能把 word1 逐个删光。
        # 这一步必须在建表前挡掉：否则 dp 只有 dp[0] 一项，内层不进，返回的是 dp[0] 而非 m
        if n == 0:
            return m

        # 滚动数组省掉的是**行**这一维；此刻 dp[j] 存的是上一行的 f[i-1][j]。
        # 初值 dp[j] = j 就是边界 f[0][j] = j：从空串出发插 j 个字符
        dp = list(range(n + 1))
        for i in range(1, m + 1):
            # 先接住旧的 dp[0]（即 f[i-1][0]），它是本行第一格的左上角；
            # 顺序颠倒成先写 dp[0] = i，第一列的左上角就变成本行的值，整行连锁出错
            diag = dp[0]
            dp[0] = i                       # 本行边界 f[i][0] = i：把 i 个字符全删光
            a = word1[i - 1]                # 本轮固定的字符，提出来省掉内层重复寻址
            for j in range(1, n + 1):
                # 必须在覆盖 dp[j] 之前取出：此刻它仍是上一行的 f[i-1][j]，即「上」
                up = dp[j]
                if a == word2[j - 1]:
                    # 末尾字符天然对齐，不花操作，直接继承左上角。
                    # 写成一律 1 + min(...) 再打补丁，会在等值时凭空多算一次操作
                    dp[j] = diag
                else:
                    left = dp[j - 1]        # 本行已更新过的一格，即 f[i][j-1]
                    # 三个来源各对应一种操作：
                    #   diag = f[i-1][j-1] -> 替换，把 a 改成 b，两端各消费一个字符
                    #   up   = f[i-1][j]   -> 删除，把 a 从 word1 里去掉
                    #   left = f[i][j-1]   -> 插入，在 word1 末尾补上 b
                    # 手写三路比较而非 min()，省掉 2.5e5 次函数调用，语义不变
                    dp[j] = 1 + (diag if diag <= up and diag <= left
                                 else up if up <= left else left)
                # 下一列的「左上」正是本列的「上」；漏掉这一步 diag 会一直停在行首旧值
                diag = up
        return dp[n]

LC72 编辑距离¶