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

题目描述
给定两个字符串 s1 和 s2，其中可能包含通配符 *。通配符 * 可以匹配任意字符（包括空字符）。要求找到 s1 和 s2 的最长公共子序列（LCS）的长度。
例如：

• 输入：s1 = "a*b", s2 = "ayb"，输出：3（LCS 为 "ayb"，* 匹配 "y"）
• 输入：s1 = "a*b", s2 = "ab"，输出：2（LCS 为 "ab"，* 匹配空字符）
• 输入：s1 = "a*b", s2 = "a**b"，输出：4（LCS 为 "a**b"，* 匹配 * 或空字符）

解题过程

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

   • i 的取值范围：0 ≤ i ≤ len(s1)
   • j 的取值范围：0 ≤ j ≤ len(s2)

2. 初始化

   • 当 i = 0 或 j = 0 时，一个字符串为空，LCS 长度为 0：
     dp[0][j] = 0（对任意 j）
     dp[i][0] = 0（对任意 i）

3. 状态转移方程
   考虑 s1[i-1] 和 s2[j-1]（因为字符串索引从 0 开始）：

   • 情况 1：s1[i-1] 和 s2[j-1] 都是普通字符且相等（如 'a' == 'a'）
     当前字符匹配，LCS 长度加 1：
     dp[i][j] = dp[i-1][j-1] + 1
   • 情况 2：s1[i-1] 或 s2[j-1] 是通配符 *
     通配符可以匹配任意字符（包括空字符），因此有三种选择：
     • 匹配 s2[j-1] 到 s1[i-1]（如果 s1[i-1] 是 *，它可以匹配 s2[j-1]）
     • 匹配空字符（跳过当前通配符）
       综合后，状态转移为：
       dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + 1)
     • dp[i-1][j]：忽略 s1[i-1]（通配符匹配空字符）
     • dp[i][j-1]：忽略 s2[j-1]（通配符匹配空字符）
     • dp[i-1][j-1] + 1：通配符匹配对方字符（视为普通字符匹配）
   • 情况 3：字符不匹配且无非通配符
     取之前状态的较大值：
     dp[i][j] = max(dp[i-1][j], dp[i][j-1])

   简化后，通用转移方程：

   if s1[i-1] == s2[j-1] 或 任一为 '*'：
       dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + 1)
   else:
       dp[i][j] = max(dp[i-1][j], dp[i][j-1])
   

4. 遍历顺序
   按 i 从 1 到 len(s1)，j 从 1 到 len(s2) 顺序遍历，确保子问题已计算。

5. 答案提取
   最终结果在 dp[len(s1)][len(s2)]。

示例演示
以 s1 = "a*b", s2 = "ayb" 为例：

• 初始化二维表（行对应 s1，列对应 s2），第一行/列为 0。
• 填表过程：
  • i=1, j=1：'a' == 'a' → dp[1][1] = dp[0][0] + 1 = 1
  • i=1, j=2：'a' 与 'y' 不匹配，但 s1[1] 是 '*'（注意索引）？实际应检查 i=2, j=2：
    • 正确流程：
      i=2, j=2：s1[1] = '*', s2[1] = 'y' → 通配符匹配，取 max(dp[1][2], dp[2][1], dp[1][1]+1) = max(1, 1, 1+1)=2
  • 最终 dp[3][3] = 3，对应 LCS "ayb"。

复杂度分析

• 时间复杂度：O(nm)，其中 n 和 m 为两字符串长度。
• 空间复杂度：可优化至 O(min(n, m))。