目录

0730:统计不同回文子序列(★★)

力扣第 730 题

题目

给你一个字符串 s ,返回 s 中不同的非空回文子序列个数 。由于答案可能很大,请返回对 109 + 7 取余 的结果。

字符串的子序列可以经由字符串删除 0 个或多个字符获得。

如果一个序列与它反转后的序列一致,那么它是回文序列。

如果存在某个 i , 满足 ai != bi ,则两个序列 a1, a2, ...b1, b2, ... 不同。

示例 1:

输入:s = 'bccb'
输出:6
解释:6 个不同的非空回文子字符序列分别为:'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。
注意:'bcb' 虽然出现两次但仅计数一次。

示例 2:

输入:s = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'
输出:104860361
解释:共有 3104860382 个不同的非空回文子序列,104860361 是对 109 + 7 取余后的值。

提示:

  • 1 <= s.length <= 1000
  • s[i] 仅包含 'a', 'b', 'c''d'

相似问题:

分析

不考虑重复的话,就是一般的区间 dp 问题,按序列最外层的字符递推。

考虑重复的话要复杂很多。假设最外层字符为 ‘a’,位置分别为 i、j,那么:

  • [i,j] 范围内最外层为 ‘b’/‘c’/’d’ 的不同回文子序列,加上 ‘a’ 后显然是不同的
  • [i,j] 范围内最外层为 ‘a’ 的不同回文子序列,加上 ‘a’ 后也是不同的
    • 但加/不加 ‘a’ 的两个集合是有很多重复的
    • 观察发现,加上 ‘a’ 后基本包括了不加 ‘a’ 的集合,除了 ‘a’ 和 ‘aa’
    • 两个集合的大小是相同的,因此加/不加 ‘a’ 的合集只比不加 ‘a’ 的集合多 2

于是令 dp[i][j][x] 代表 [i,j] 范围内最外层为字符 x 的不同回文子序列个数,即可区间递推。

为了方便,可以将 s 的字符都转为整数。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def countPalindromicSubsequences(self, s: str) -> int:
    n, mod = len(s), 10**9+7
    A = [ord(c)-ord('a') for c in s]
    dp = [[[0]*4 for _ in range(n)] for _ in range(n)]
    for j in range(n):
        dp[j][j][A[j]] = 1
        for i in range(j-1, -1, -1):
            dp[i][j] = dp[i+1][j-1][:]
            if A[i]==A[j]:
                dp[i][j][A[i]] = (sum(dp[i+1][j-1])+2)%mod
            else:
                dp[i][j][A[i]] = dp[i][j-1][A[i]]
                dp[i][j][A[j]] = dp[i+1][j][A[j]]
    return sum(dp[0][-1])%mod

3408 ms