数据结构与算法 / 系统课时

用二维状态处理字符串匹配

用二维状态处理字符串匹配

两个字符串一起变化时,只用一个下标往往无法描述“各自处理到哪里”。二维动态规划把两个前缀位置同时放进状态,让匹配、跳过、替换等操作都有明确来源。本篇以最长公共子序列为主例,并把同一建模方式迁移到编辑距离和其他前缀匹配问题。

学习目标

  • 用两个位置维度定义字符串前缀状态
  • 从字符是否相等推导二维状态的转移来源
  • 根据依赖方向确定初始化与遍历顺序

二维状态为什么适合字符串匹配

给定字符串 s 和 t,常见问题都会同时问“s 处理到第几个字符”和“t 处理到第几个字符”。因此可以定义:

dp[i][j] 表示只考虑 s 的前 i 个字符和 t 的前 j 个字符时的答案。

这个定义把两个字符串都截成前缀,状态 (i, j) 就是网格中的一个格子。转移通常来自左侧 (i, j-1)、上侧 (i-1, j) 或左上角 (i-1, j-1),具体选择取决于当前两个字符是否匹配以及题目允许什么操作。

字符串二维动态规划状态依赖网格

二维表的第 0 行和第 0 列代表其中一个字符串为空。它们不是额外技巧,而是把边界情况纳入统一状态定义:只要初始化正确,后面的转移就不需要不断判断是否越界。

最长公共子序列的转移

最长公共子序列要求字符相对顺序不变,但不要求连续。定义 dp[i][j] 为 s[:i] 与 t[:j] 的最长公共子序列长度。

若 s[i-1] == t[j-1],这两个字符可以共同接在更短前缀的答案后面:

dp[i][j]=dp[i−1][j−1]+1dp[i][j] = dp[i-1][j-1] + 1

若二者不同,当前字符至少有一个不能出现在同一个最优公共子序列中,因此比较“丢掉 s 当前字符”和“丢掉 t 当前字符”:

dp[i][j]=max⁡(dp[i−1][j],dp[i][j−1])dp[i][j] = \max(dp[i-1][j], dp[i][j-1])

因为当前格只依赖左、上、左上三个已经计算过的状态,所以按行从左到右填表即可。

写出完整实现并验证

下面的程序计算两个字符串的最长公共子序列长度,并打印最终二维表,便于检查边界与转移是否符合定义。

python
def lcs_length(s, t):
    rows, cols = len(s) + 1, len(t) + 1
    dp = [[0] * cols for _ in range(rows)]

    for i in range(1, rows):
        for j in range(1, cols):
            if s[i - 1] == t[j - 1]:
                # 两个当前字符匹配,答案来自左上角再加 1。
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                # 不匹配时至少跳过一个当前字符。
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[-1][-1], dp


if __name__ == "__main__":
    length, table = lcs_length("abcde", "ace")
    print("length:", length)
    for row in table:
        print(row)

预期输出

text
length: 3
[0, 0, 0, 0]
[0, 1, 1, 1]
[0, 1, 1, 1]
[0, 1, 2, 2]
[0, 1, 2, 2]
[0, 1, 2, 3]

最后一个格子是 3,对应公共子序列 ace。如果某一行或某一列突然出现不符合单调性的值,通常说明字符下标 i-1、j-1 与状态下标 i、j 混用了。

同一张二维表如何迁移到其他题

二维字符串 DP 的关键不是记住某个公式,而是先回答“状态代表哪两个前缀”,再根据允许操作选择来源。

问题 dp[i][j] 常见含义 主要来源
最长公共子序列 两个前缀的 LCS 长度 左、上、左上
编辑距离 把 s[:i] 变成 t[:j] 的最少操作数 删除、插入、替换对应的三个邻格
通配或正则式匹配 两个前缀是否能够匹配 由当前模式字符决定左、上或左上依赖
区间或分段匹配 两个边界或前缀组合下的最优值 依题意增加区间长度或分割点维度

例如编辑距离中,若当前字符相等,通常直接继承左上角;若不同,则从删除、插入、替换三个操作中取最小值再加 1。它与 LCS 使用的是同一个二维前缀坐标系,只是状态值和转移规则不同。

检查二维字符串 DP 的三个边界

最常见的错误集中在状态定义与下标错一位:

  1. 第 0 行和第 0 列代表什么。 LCS 中它们全是 0;编辑距离中通常需要初始化为 0,1,2,...,因为空串转换到长度为 j 的前缀需要 j 次插入。
  2. 字符下标与状态下标要错开一位。 状态 i 表示前 i 个字符,因此当前字符是 s[i-1],不是 s[i]。
  3. 遍历方向必须覆盖依赖。 如果当前格依赖左、上和左上,就必须保证这些格子已经计算完成;标准二维表按行从左到右即可。

掌握二维字符串 DP 后,真正可复用的是“两个前缀位置组成坐标”的建模方式。只要先写清 dp[i][j] 的含义,再标出当前格能从哪些已知状态转移,初始化、遍历顺序和边界通常都会自然确定。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用二维状态处理字符串匹配

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通