线性动态规划：最长公共子序列的变种——带通配符的最长公共子序列

题目描述
给定两个字符串 s1 和 s2，其中 s1 可能包含通配符 '?'，它可以匹配任意单个字符（包括 s2 中的任何字符）。要求找出 s1 和 s2 的最长公共子序列（LCS）的长度。注意：通配符 '?' 在匹配时不视为常规字符，而是作为万能符参与匹配，但匹配的字符仍需计入 LCS 长度。

示例

• 输入：s1 = "a?c", s2 = "acb"
  输出：3
  解释：通配符 '?' 匹配 'b'，LCS 为 "acb"，长度为 3。
• 输入：s1 = "a??b", s2 = "axcyb"
  输出：4
  解释：通配符匹配 'x' 和 'y'，LCS 为 "axcyb" 的子序列（如 "axyb"），但需注意 LCS 需同时是 s1（通配符替换后）和 s2 的子序列。

解题过程

步骤 1：定义状态
使用动态规划表 dp[i][j]，表示 s1 的前 i 个字符（含通配符）与 s2 的前 j 个字符的带通配符 LCS 长度。

• i 范围：0 到 len(s1)（i=0 表示空字符串）
• j 范围：0 到 len(s2)

步骤 2：状态转移方程
分情况讨论：

1. 基础情况：

   • 若 i=0 或 j=0，则 dp[i][j] = 0（空字符串无公共子序列）。

2. 当 s1[i-1] 是通配符 '?'：

   • 通配符可匹配 s2[j-1]，因此当前字符可匹配，等价于两字符串均跳过当前字符：
     dp[i][j] = dp[i-1][j-1] + 1
   • 但需注意：通配符也可选择不匹配（例如为了后续更优解），因此还需考虑跳过 s1 当前字符或跳过 s2 当前字符的情况：
     dp[i][j] = max(dp[i-1][j-1] + 1, dp[i-1][j], dp[i][j-1])

3. 当 s1[i-1] 不是通配符：

   • 若 s1[i-1] == s2[j-1]，则当前字符匹配：
     dp[i][j] = dp[i-1][j-1] + 1
   • 否则，当前字符不匹配，继承跳过 s1 或 s2 当前字符的最大值：
     dp[i][j] = max(dp[i-1][j], dp[i][j-1])

整理转移方程：

if i == 0 or j == 0:
    dp[i][j] = 0
elif s1[i-1] == '?':
    dp[i][j] = max(dp[i-1][j-1] + 1, dp[i-1][j], dp[i][j-1])
else:
    if s1[i-1] == s2[j-1]:
        dp[i][j] = dp[i-1][j-1] + 1
    else:
        dp[i][j] = max(dp[i-1][j], dp[i][j-1])

步骤 3：初始化与填表

• 初始化二维数组 dp，尺寸为 (len(s1)+1) x (len(s2)+1)，第一行和第一列全 0。
• 按 i 从 1 到 len(s1)、j 从 1 到 len(s2) 的顺序填表。

步骤 4：举例验证
以 s1 = "a?c", s2 = "acb" 为例：

   '' a  c  b
'' 0  0  0  0
a  0  1  1  1
?  0  1  2  2  // '?' 匹配 'c' 得 2，或跳过得 1，取最大值 2
c  0  1  2  3  // 'c' 匹配 'c'，由 dp[2][2]+1=3

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

步骤 5：复杂度分析

• 时间复杂度：O(mn)，其中 m = len(s1)，n = len(s2)。
• 空间复杂度：可优化至 O(n)（使用滚动数组）。

核心思路总结
通配符 '?' 的灵活性体现在状态转移中需同时考虑“匹配当前字符”和“跳过字符”的多种情况，通过取最大值保证最优解。此解法扩展了经典 LCS 问题，适用于含模糊匹配的场景。