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

字数 2773 2025-11-02 10:11:13

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

题目描述
给定两个字符串 s1 和 s2，其中 s1 可能包含通配符 *，* 可以匹配任意字符（包括空字符）。要求找出 s1 和 s2 的最长公共子序列（LCS），但需满足以下条件：

通配符 * 可以匹配 s2 中的任意一个字符（包括连续多个字符的匹配，但需保持顺序），也可以匹配空字符（即不匹配任何字符）。
其他字符必须精确匹配。

例如：

s1 = "a*b*c"，s2 = "aXYbZc"，LCS 为 "aXYbZc"（* 匹配了 "XY" 和 "Z"）。
s1 = "a**b"，s2 = "aXb"，LCS 为 "aXb"（第一个 * 匹配 "X"，第二个 * 匹配空）。

解题过程

步骤1：定义状态
设 dp[i][j] 表示 s1 的前 i 个字符与 s2 的前 j 个字符的最长公共子序列长度。

i 的范围是 0 到 len(s1)，j 的范围是 0 到 len(s2)。
当 i=0 或 j=0 时，表示一个字符串为空，此时 LCS 长度为 0。

步骤2：状态转移方程
针对 s1[i-1] 和 s2[j-1]（因为字符串索引从 0 开始）：

如果 s1[i-1] 是通配符 *：
- * 可以匹配空字符：dp[i][j] = dp[i-1][j]。
- * 可以匹配 s2[j-1]：dp[i][j] = dp[i][j-1]。
- 综合两种情况，取最大值：dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
如果 s1[i-1] 不是通配符：
- 若 s1[i-1] == s2[j-1]：当前字符匹配，dp[i][j] = dp[i-1][j-1] + 1。
- 否则：当前字符不匹配，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

步骤3：初始化

dp[0][j] = 0（s1 为空时，LCS 长度为 0）。
dp[i][0] = 0（s2 为空时，LCS 长度为 0）。

步骤4：计算顺序
按 i 从 1 到 len(s1)，j 从 1 到 len(s2) 的顺序填充 dp 表。

步骤5：举例说明
以 s1 = "a*b"，s2 = "aXb" 为例：

初始化 dp 表（尺寸 4×4，因字符串长度分别为 3 和 3）：

    "" "a" "X" "b"
""  0   0   0   0
"a" 0   ... ...
"*" 0   ... ...
"b" 0   ... ...

填充过程：
- i=1, j=1：s1[0]='a' 匹配 s2[0]='a'，dp[1][1] = dp[0][0] + 1 = 1。
- i=1, j=2：'a' 不匹配 'X'，取 max(dp[0][2]=0, dp[1][1]=1) = 1。
- i=1, j=3：'a' 不匹配 'b'，取 max(dp[0][3]=0, dp[1][2]=1) = 1。
- i=2, j=1：s1[1]='*'，取 max(dp[1][1]=1, dp[2][0]=0) = 1。
- i=2, j=2：'*' 匹配 'X' 或空，取 max(dp[1][2]=1, dp[2][1]=1) = 1。
- i=2, j=3：'*' 匹配 'b' 或空，取 max(dp[1][3]=1, dp[2][2]=1) = 1。
- i=3, j=3：s1[2]='b' 匹配 s2[2]='b'，dp[3][3] = dp[2][2] + 1 = 2。
最终 dp[3][3] = 2，但实际 LCS 应为 "aXb" 长度 3？注意：这里 dp 定义是子序列长度，但 * 匹配了 'X'，所以整个 s2 被匹配，长度应为 3。修正：
- 在 i=2, j=2 时，'*' 匹配 'X'，应允许 dp[2][2] = dp[1][1] + 1 = 2？
- 问题出在：* 匹配一个字符时，应视为一次匹配，因此状态转移需调整。

修正状态转移方程
若 s1[i-1] 是 *：

匹配空：dp[i][j] = dp[i-1][j]。
匹配 s2[j-1]：dp[i][j] = dp[i-1][j-1] + 1（因为 * 匹配了当前字符）。
还需考虑 * 匹配多个字符的情况：dp[i][j] = dp[i][j-1]（但此时 * 已匹配 s2[j-1]，继续匹配前一个字符？）。
实际上，更准确的方式是：
dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + 1)，但这样会重复计数。

正确解法
标准解法是：

* 匹配空：dp[i][j] = dp[i-1][j]。
* 匹配 s2 的当前字符：dp[i][j] = dp[i][j-1]。
但这样无法处理 * 匹配多个字符的情况。实际上，此问题应转化为：s1 中的 * 可匹配 s2 的任意子串（包括空），因此需允许 * 匹配一段连续字符。
更精确的状态转移：

若 s1[i-1] == '*'：
dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + 1)？但这样仍不完善。
实际应采用：
dp[i][j] = max(dp[i-1][j], dp[i][j-1])，并额外处理 * 匹配多个字符的情况，但通常这类问题需用贪心或回溯，严格动态规划需三维状态（记录 * 匹配的字符数）。

简化版本
在大多数面试中，只需处理 * 匹配任意字符（非空）的情况，即：

若 s1[i-1] == '*'：dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + 1)。
但需注意：dp[i-1][j-1] + 1 覆盖了 * 匹配单个字符的情况，而 dp[i][j-1] 覆盖了匹配多个字符的情况。

最终答案
对于 s1 = "a*b", s2 = "aXb"：

使用修正方程后，dp[3][3] = 3，LCS 为 "aXb"。

总结
带通配符的 LCS 问题需根据通配符的语义调整状态转移方程，重点在于处理通配符匹配空字符、单个字符或连续字符的不同情况。

线性动态规划：最长公共子序列的变种——带通配符的最长公共子序列（进阶版：允许通配符匹配任意字符且通配符可匹配空字符）题目描述给定两个字符串 s1 和 s2 ，其中 s1 可能包含通配符 * ， * 可以匹配任意字符（包括空字符）。要求找出 s1 和 s2 的最长公共子序列（LCS），但需满足以下条件：通配符 * 可以匹配 s2 中的任意一个字符（包括连续多个字符的匹配，但需保持顺序），也可以匹配空字符（即不匹配任何字符）。其他字符必须精确匹配。例如： s1 = "a*b*c" ， s2 = "aXYbZc" ，LCS 为 "aXYbZc" （ * 匹配了 "XY" 和 "Z" ）。 s1 = "a**b" ， s2 = "aXb" ，LCS 为 "aXb" （第一个 * 匹配 "X" ，第二个 * 匹配空）。解题过程步骤1：定义状态设 dp[i][j] 表示 s1 的前 i 个字符与 s2 的前 j 个字符的最长公共子序列长度。 i 的范围是 0 到 len(s1) ， j 的范围是 0 到 len(s2) 。当 i=0 或 j=0 时，表示一个字符串为空，此时 LCS 长度为 0。步骤2：状态转移方程针对 s1[i-1] 和 s2[j-1] （因为字符串索引从 0 开始）：如果 s1[i-1] 是通配符 * ： * 可以匹配空字符： dp[i][j] = dp[i-1][j] 。 * 可以匹配 s2[j-1] ： dp[i][j] = dp[i][j-1] 。综合两种情况，取最大值： dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 。如果 s1[i-1] 不是通配符：若 s1[i-1] == s2[j-1] ：当前字符匹配， dp[i][j] = dp[i-1][j-1] + 1 。否则：当前字符不匹配， dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 。步骤3：初始化 dp[0][j] = 0 （ s1 为空时，LCS 长度为 0）。 dp[i][0] = 0 （ s2 为空时，LCS 长度为 0）。步骤4：计算顺序按 i 从 1 到 len(s1) ， j 从 1 到 len(s2) 的顺序填充 dp 表。步骤5：举例说明以 s1 = "a*b" ， s2 = "aXb" 为例：初始化 dp 表（尺寸 4×4，因字符串长度分别为 3 和 3）：填充过程： i=1, j=1 ： s1[0]='a' 匹配 s2[0]='a' ， dp[1][1] = dp[0][0] + 1 = 1 。 i=1, j=2 ： 'a' 不匹配 'X' ，取 max(dp[0][2]=0, dp[1][1]=1) = 1 。 i=1, j=3 ： 'a' 不匹配 'b' ，取 max(dp[0][3]=0, dp[1][2]=1) = 1 。 i=2, j=1 ： s1[1]='*' ，取 max(dp[1][1]=1, dp[2][0]=0) = 1 。 i=2, j=2 ： '*' 匹配 'X' 或空，取 max(dp[1][2]=1, dp[2][1]=1) = 1 。 i=2, j=3 ： '*' 匹配 'b' 或空，取 max(dp[1][3]=1, dp[2][2]=1) = 1 。 i=3, j=3 ： s1[2]='b' 匹配 s2[2]='b' ， dp[3][3] = dp[2][2] + 1 = 2 。最终 dp[3][3] = 2 ，但实际 LCS 应为 "aXb" 长度 3？注意：这里 dp 定义是子序列长度，但 * 匹配了 'X' ，所以整个 s2 被匹配，长度应为 3。修正：在 i=2, j=2 时， '*' 匹配 'X' ，应允许 dp[2][2] = dp[1][1] + 1 = 2 ？问题出在： * 匹配一个字符时，应视为一次匹配，因此状态转移需调整。修正状态转移方程若 s1[i-1] 是 * ：匹配空： dp[i][j] = dp[i-1][j] 。匹配 s2[j-1] ： dp[i][j] = dp[i-1][j-1] + 1 （因为 * 匹配了当前字符）。还需考虑 * 匹配多个字符的情况： dp[i][j] = dp[i][j-1] （但此时 * 已匹配 s2[j-1] ，继续匹配前一个字符？）。实际上，更准确的方式是： dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + 1) ，但这样会重复计数。正确解法标准解法是： * 匹配空： dp[i][j] = dp[i-1][j] 。 * 匹配 s2 的当前字符： dp[i][j] = dp[i][j-1] 。但这样无法处理 * 匹配多个字符的情况。实际上，此问题应转化为： s1 中的 * 可匹配 s2 的任意子串（包括空），因此需允许 * 匹配一段连续字符。更精确的状态转移：若 s1[i-1] == '*' ： dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + 1) ？但这样仍不完善。实际应采用： dp[i][j] = max(dp[i-1][j], dp[i][j-1]) ，并额外处理 * 匹配多个字符的情况，但通常这类问题需用贪心或回溯，严格动态规划需三维状态（记录 * 匹配的字符数）。简化版本在大多数面试中，只需处理 * 匹配任意字符（非空）的情况，即：若 s1[i-1] == '*' ： dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + 1) 。但需注意： dp[i-1][j-1] + 1 覆盖了 * 匹配单个字符的情况，而 dp[i][j-1] 覆盖了匹配多个字符的情况。最终答案对于 s1 = "a*b" , s2 = "aXb" ：使用修正方程后， dp[3][3] = 3 ，LCS 为 "aXb" 。总结带通配符的 LCS 问题需根据通配符的语义调整状态转移方程，重点在于处理通配符匹配空字符、单个字符或连续字符的不同情况。