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

字数 1249 2025-11-01 09:19:10

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

题目描述
给定两个字符串 s1 和 s2，其中 s1 可能包含通配符 *，* 可以匹配任意字符（包括空字符）。要求找出 s1 和 s2 的最长公共子序列（LCS）长度。注意：s1 中的 * 可以匹配 s2 中的任意连续子串（包括空串），且 * 可以多次使用，但需按顺序匹配。

示例

输入：s1 = "a*b", s2 = "acb"
输出：3（* 匹配 "c"，LCS 为 "acb"）
输入：s1 = "a*b*c", s2 = "axyzbzc"
输出：6（* 依次匹配 "xy" 和 "z"，LCS 为 "axyzbzc"）

解题过程

步骤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] 不是通配符 *：
- 若 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])
s1[i-1] 是通配符 *：
- * 可以匹配空字符（即跳过 s1 的 *）：
  option1 = dp[i-1][j]
- * 可以匹配 s2 的当前字符 s2[j-1]，并继续匹配 s2 的更多字符：
  option2 = dp[i][j-1]
- 综合两种情况：
  dp[i][j] = max(option1, option2)

步骤3：初始化

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

步骤4：递推顺序
按 i 从 1 到 len(s1)，j 从 1 到 len(s2) 顺序计算。

步骤5：举例验证
以 s1 = "a*b", s2 = "acb" 为例：

初始化二维表（行列分别表示 s1 和 s2 的前缀长度）：

    "" a  c  b
""  0  0  0  0
a   0  1  1  1
*   0  1  1  2
b   0  1  1  3

最终结果 dp[3][3] = 3，符合预期。

关键点

通配符 * 的匹配灵活性通过 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 体现，允许跳过或匹配多个字符。
本质是经典 LCS 的扩展，需正确处理 * 的两种匹配方式。

通过以上步骤，可高效求出带通配符的最长公共子序列长度。

线性动态规划：最长公共子序列的变种——带通配符的最长公共子序列（进阶版：允许通配符匹配任意字符且通配符可匹配空字符）题目描述给定两个字符串 s1 和 s2 ，其中 s1 可能包含通配符 * ， * 可以匹配任意字符（包括空字符）。要求找出 s1 和 s2 的最长公共子序列（LCS）长度。注意： s1 中的 * 可以匹配 s2 中的任意连续子串（包括空串），且 * 可以多次使用，但需按顺序匹配。示例输入： s1 = "a*b", s2 = "acb" 输出：3（ * 匹配 "c" ，LCS 为 "acb" ）输入： s1 = "a*b*c", s2 = "axyzbzc" 输出：6（ * 依次匹配 "xy" 和 "z" ，LCS 为 "axyzbzc" ）解题过程步骤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] 不是通配符 * ：若 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]) s1[i-1] 是通配符 * ： * 可以匹配空字符（即跳过 s1 的 * ）： option1 = dp[i-1][j] * 可以匹配 s2 的当前字符 s2[j-1] ，并继续匹配 s2 的更多字符： option2 = dp[i][j-1] 综合两种情况： dp[i][j] = max(option1, option2) 步骤3：初始化 dp[0][j] = 0 （ s1 为空时，LCS 长度为 0） dp[i][0] = 0 （ s2 为空时，LCS 长度为 0）步骤4：递推顺序按 i 从 1 到 len(s1) ， j 从 1 到 len(s2) 顺序计算。步骤5：举例验证以 s1 = "a*b", s2 = "acb" 为例：初始化二维表（行列分别表示 s1 和 s2 的前缀长度）：最终结果 dp[3][3] = 3 ，符合预期。关键点通配符 * 的匹配灵活性通过 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 体现，允许跳过或匹配多个字符。本质是经典 LCS 的扩展，需正确处理 * 的两种匹配方式。通过以上步骤，可高效求出带通配符的最长公共子序列长度。