线性动态规划：最长公共子序列的变种——带通配符的最长公共子序列（进阶版：允许通配符匹配任意字符且通配符可匹配空字符）

字数 1779 2025-10-30 17:43:25

线性动态规划：最长公共子序列的变种——带通配符的最长公共子序列（进阶版：允许通配符匹配任意字符且通配符可匹配空字符）

题目描述

给定两个字符串 s 和 t，其中字符串 t 可能包含通配符 *。通配符 * 可以匹配任意长度的字符序列（包括空序列）。求 s 和 t 的最长公共子序列（LCS）长度，其中 t 中的通配符可以匹配 s 中的任意连续子串。

示例
输入：
s = "abcde"
t = "a*c*e"
输出：5
解释：通配符 * 可以匹配 "b" 和 "d"，因此整个 s 都是匹配的。

解题思路

关键点

通配符 * 可以匹配任意长度的子串（包括空串），这相当于在匹配过程中允许跳过 s 的任意连续部分。
需要设计动态规划状态，区分普通字符匹配和通配符的灵活性。

状态定义

定义 dp[i][j] 表示 s 的前 i 个字符和 t 的前 j 个字符的最长公共子序列长度。

状态转移方程

普通字符匹配：
若 t[j-1] 不是通配符 *，则需检查 s[i-1] 和 t[j-1] 是否匹配：
- 如果 s[i-1] == t[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1。
- 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])（继承之前的最优解）。
通配符匹配：
若 t[j-1] 是通配符 *，则它可以选择匹配 s 中从当前位置开始的任意长度子串（包括空串）。此时：
- 匹配空串：dp[i][j] = dp[i][j-1]（跳过 t 的通配符）。
- 匹配一个或多个字符：dp[i][j] = dp[i-1][j]（利用 * 匹配 s[i-1]，并继续允许 * 匹配更多字符）。
- 综合两种情况：dp[i][j] = max(dp[i][j-1], dp[i-1][j])。

初始化

dp[0][j]：当 s 为空时，若 t 的前 j 个字符全是 *，则匹配长度为 0（因为 * 可匹配空串）；否则为 0（无法匹配非通配符）。
dp[i][0]：当 t 为空时，匹配长度恒为 0。

详细步骤

初始化二维数组 dp，大小为 (len(s)+1) x (len(t)+1)，所有元素初始为 0。
遍历 i 从 1 到 len(s)，j 从 1 到 len(t)：
- 如果 t[j-1] == '*'：
  - dp[i][j] = max(dp[i][j-1], dp[i-1][j])
- 否则：
  - 如果 s[i-1] == t[j-1]：
    - dp[i][j] = dp[i-1][j-1] + 1
  - 否则：
    - dp[i][j] = max(dp[i-1][j], dp[i][j-1])
最终结果在 dp[len(s)][len(t)]。

示例推导

以 s = "abcde"、t = "a*c*e" 为例：

初始化 dp 表（行索引 i 对应 s，列索引 j 对应 t）：

   t: a * c * e
s:0 0 0 0 0 0
a:0
b:0
c:0
d:0
e:0

逐步填充：

i=1, j=1：s[0]='a' 匹配 t[0]='a'，dp[1][1] = dp[0][0]+1 = 1。
i=1, j=2：t[1]='*'，dp[1][2] = max(dp[1][1], dp[0][2]) = max(1,0) = 1。
i=2, j=2：t[1]='*'，dp[2][2] = max(dp[2][1], dp[1][2]) = max(0,1) = 1（注意 dp[2][1] 未匹配，为 0）。
继续推导，最终 dp[5][5] = 5，表示整个 s 被匹配。

复杂度分析

时间复杂度：O(mn)，其中 m 和 n 分别是 s 和 t 的长度。
空间复杂度：O(mn)，可优化至 O(n)（仅保留前一行的状态）。

总结

本题通过扩展经典 LCS 问题，引入通配符的灵活匹配机制。关键点在于处理 * 时，同时考虑跳过通配符或利用它匹配当前字符，并通过动态规划的状态转移覆盖所有可能情况。

线性动态规划：最长公共子序列的变种——带通配符的最长公共子序列（进阶版：允许通配符匹配任意字符且通配符可匹配空字符）题目描述给定两个字符串 s 和 t ，其中字符串 t 可能包含通配符 * 。通配符 * 可以匹配任意长度的字符序列（包括空序列）。求 s 和 t 的最长公共子序列（LCS）长度，其中 t 中的通配符可以匹配 s 中的任意连续子串。示例输入： s = "abcde" t = "a*c*e" 输出： 5 解释：通配符 * 可以匹配 "b" 和 "d" ，因此整个 s 都是匹配的。解题思路关键点通配符 * 可以匹配任意长度的子串（包括空串），这相当于在匹配过程中允许跳过 s 的任意连续部分。需要设计动态规划状态，区分普通字符匹配和通配符的灵活性。状态定义定义 dp[i][j] 表示 s 的前 i 个字符和 t 的前 j 个字符的最长公共子序列长度。状态转移方程普通字符匹配：若 t[j-1] 不是通配符 * ，则需检查 s[i-1] 和 t[j-1] 是否匹配：如果 s[i-1] == t[j-1] ，则 dp[i][j] = dp[i-1][j-1] + 1 。否则， dp[i][j] = max(dp[i-1][j], dp[i][j-1]) （继承之前的最优解）。通配符匹配：若 t[j-1] 是通配符 * ，则它可以选择匹配 s 中从当前位置开始的任意长度子串（包括空串）。此时：匹配空串： dp[i][j] = dp[i][j-1] （跳过 t 的通配符）。匹配一个或多个字符： dp[i][j] = dp[i-1][j] （利用 * 匹配 s[i-1] ，并继续允许 * 匹配更多字符）。综合两种情况： dp[i][j] = max(dp[i][j-1], dp[i-1][j]) 。初始化 dp[0][j] ：当 s 为空时，若 t 的前 j 个字符全是 * ，则匹配长度为 0（因为 * 可匹配空串）；否则为 0（无法匹配非通配符）。 dp[i][0] ：当 t 为空时，匹配长度恒为 0。详细步骤初始化二维数组 dp ，大小为 (len(s)+1) x (len(t)+1) ，所有元素初始为 0。遍历 i 从 1 到 len(s) ， j 从 1 到 len(t) ：如果 t[j-1] == '*' ： dp[i][j] = max(dp[i][j-1], dp[i-1][j]) 否则：如果 s[i-1] == t[j-1] ： dp[i][j] = dp[i-1][j-1] + 1 否则： dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 最终结果在 dp[len(s)][len(t)] 。示例推导以 s = "abcde" 、 t = "a*c*e" 为例：初始化 dp 表（行索引 i 对应 s ，列索引 j 对应 t ）：逐步填充： i=1, j=1 ： s[0]='a' 匹配 t[0]='a' ， dp[1][1] = dp[0][0]+1 = 1 。 i=1, j=2 ： t[1]='*' ， dp[1][2] = max(dp[1][1], dp[0][2]) = max(1,0) = 1 。 i=2, j=2 ： t[1]='*' ， dp[2][2] = max(dp[2][1], dp[1][2]) = max(0,1) = 1 （注意 dp[2][1] 未匹配，为 0）。继续推导，最终 dp[5][5] = 5 ，表示整个 s 被匹配。复杂度分析时间复杂度：O(mn)，其中 m 和 n 分别是 s 和 t 的长度。空间复杂度：O(mn)，可优化至 O(n)（仅保留前一行的状态）。总结本题通过扩展经典 LCS 问题，引入通配符的灵活匹配机制。关键点在于处理 * 时，同时考虑跳过通配符或利用它匹配当前字符，并通过动态规划的状态转移覆盖所有可能情况。