判断字符串是否存在长度为k的回文子序列的O(k²)动态规划算法

问题描述 #

给定由小写英文字母组成的字符串S，判断该字符串是否包含长度恰好为k的回文子序列，要求实现时间复杂度为O(k²)的动态规划算法。

示例：

• 输入：S= "abacd", K = 3 → 输出：True（例如子序列"aba"或"aca"）
• 输入：S= "abacd", K = 4 → 输出：False（无法找到长度为4的回文子序列）

核心思路 #

回文的本质是对称结构，我们不需要枚举所有子序列（这会带来O(n²)的时间复杂度），而是通过动态规划跟踪构建对称回文的状态。由于k通常远小于字符串长度n，我们可以用一个大小为(k+1)×(k+1)的DP数组来记录状态，结合小写字母仅26种的特性，将时间复杂度控制在O(k²)。

DP状态定义 #

定义dp[l][r]为：是否能构建一个回文框架，其中左边还需补充l个字符，右边还需补充r个字符，且左右补充的字符必须对称匹配（即左边第1个补充字符需等于右边第1个补充字符，以此类推）。

• 当l + r == 0：说明已构建出完整的回文（长度为k）；
• 当l + r == 1：说明只需任意一个字符即可补全为长度k的回文（对应k为奇数的场景）。

初始状态：dp[0][0] = True（空框架是合法的初始状态）。

算法步骤 #

1. 预处理字符位置：统计每个字符在字符串中出现的所有索引位置，快速判断是否存在可匹配的字符对。
2. 初始化DP数组：创建一个(k+1)×(k+1)的布尔数组，所有值初始化为False，仅dp[0][0] = True。
3. 状态转移：
   • 按回文构建的阶段迭代，遍历所有dp[l][r] = True的状态：
     • 对每个出现次数≥2的字符c：
       • 若l > 0：用c匹配左边待补充的一个字符，更新dp[l-1][r] = True；
       • 若r > 0：用c匹配右边待补充的一个字符，更新dp[l][r-1] = True；
       • 若l < k//2：将c作为左边新的待匹配字符，更新dp[l+1][r] = True；
       • 若r < k//2：将c作为右边新的待匹配字符，更新dp[l][r+1] = True；
4. 结果判断：
   • 若k为偶数：检查dp[0][0]是否为True（说明已凑齐k/2对对称字符）；
   • 若k为奇数：检查dp[0][0]、dp[0][1]或dp[1][0]是否为True（说明已凑齐(k-1)/2对对称字符，加上任意一个中间字符即可）。

代码实现（Python） #

def has_palindrome_subsequence(s, k):
    if k == 1:
        return True
    if k == 0:
        return False
    
    # 预处理每个字符的出现位置
    char_positions = {}
    for idx, c in enumerate(s):
        char_positions.setdefault(c, []).append(idx)
    
    max_half = k // 2
    dp = [[False]*(k+1) for _ in range(k+1)]
    dp[0][0] = True
    
    # 按阶段更新状态，确保核心逻辑时间复杂度为O(k²)
    for _ in range(max_half + 1):
        new_dp = [row.copy() for row in dp]
        for l in range(k+1):
            for r in range(k+1):
                if dp[l][r]:
                    # 遍历所有有足够出现次数的字符
                    for c in char_positions:
                        if len(char_positions[c]) >= 2:
                            if l > 0:
                                new_dp[l-1][r] = True
                            if r > 0:
                                new_dp[l][r-1] = True
                            if l < max_half:
                                new_dp[l+1][r] = True
                            if r < max_half:
                                new_dp[l][r+1] = True
        dp = new_dp
    
    if k % 2 == 0:
        return dp[0][0]
    else:
        return dp[0][0] or dp[0][1] or dp[1][0]

# 测试示例
print(has_palindrome_subsequence("abacd", 3))  # 输出 True
print(has_palindrome_subsequence("abacd", 4))  # 输出 False

复杂度分析 #

• 时间复杂度：O(k²×26) = O(k²)，其中26是小写字母的数量（常数），核心状态转移的次数为O(k²)；
• 空间复杂度：O(k²)，用于存储DP状态数组。

内容的提问来源于stack exchange，提问作者Sheldoor