最长公共子序列的变种：带通配符的最长公共子序列

字数 904 2025-10-29 21:04:18

最长公共子序列的变种：带通配符的最长公共子序列

题目描述：给定两个字符串s和t，其中字符串t可能包含通配符'?'，它可以匹配任意单个字符。求s和t的最长公共子序列的长度。

解题过程：

问题分析：
- 这是最长公共子序列(LCS)问题的变种，增加了通配符匹配的复杂性
- 通配符'?'可以匹配任意字符，这会影响状态转移方程的设计
状态定义：
- 定义dp[i][j]表示字符串s的前i个字符与字符串t的前j个字符的最长公共子序列长度
- i的范围是0到len(s)，j的范围是0到len(t)
状态转移方程：
- 当i=0或j=0时，dp[i][j] = 0（空字符串的LCS长度为0）
- 当i>0且j>0时：
  a) 如果t的第j个字符是通配符'?'：
  通配符可以匹配s的第i个字符，所以：dp[i][j] = dp[i-1][j-1] + 1
  b) 如果t的第j个字符不是通配符，且s[i-1] == t[j-1]：
  字符匹配：dp[i][j] = dp[i-1][j-1] + 1
  c) 如果字符不匹配：
  考虑两种情况的最大值：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
边界条件处理：
- dp[0][j] = 0（空s字符串与任何字符串的LCS为0）
- dp[i][0] = 0（空t字符串与任何字符串的LCS为0）
算法实现步骤：
- 初始化二维dp数组，大小为(len(s)+1) × (len(t)+1)
- 按行遍历，从i=1到len(s)，j=1到len(t)
- 根据状态转移方程填充dp数组
- 最终结果为dp[len(s)][len(t)]
时间复杂度分析：
- 需要填充O(m×n)的二维表格，其中m=len(s)，n=len(t)
- 时间复杂度为O(m×n)，空间复杂度为O(m×n)
示例验证：
以s="abcde", t="a?c?e"为例：
- 匹配过程：a匹配a，?匹配b，c匹配c，?匹配d，e匹配e
- 最长公共子序列长度为5，即整个字符串"abcde"

这个算法通过合理处理通配符的情况，扩展了经典LCS算法的应用范围。