730. Count Different Palindromic Subsequences

https://leetcode.com/problems/count-different-palindromic-subsequences/

其实这题可以化简成为,对于S[0..n-1]字符串来说:

那么如何求解S[0..n-1]头尾是'a'的回文个数呢?

所以统计去重的话,我们可以要求在统计的时候,加上某些限定的条件(比如固定某个前缀等)。一旦加上这些限定条件之后,所得到的结果肯定是不重复的。


在计算到诸如 "a…a"这样的话,是有三类选择的:

  1. 只使用a
  2. 只使用aa
  3. 使用fun(…, a/b/c/d)
def fun(s, e, c):
    if s > e:
        return 0

    key = (s, e, c)
    if key in dp:
        return dp[key]

    # print(s, e, c)
    s = search_right(s, c)
    e = search_left(e, c)
    # print(s, e)
    if s > e:
        ans = 0
    elif s == e:
        ans = 1
    else:
        ans = 2  # 'xx or x'
        for x in range(4):
            ans += fun(s + 1, e - 1, x)
            ans = ans % P
    dp[key] = ans
    return ans

然后另外一个关键就是如何实现 `search_left` 和 `search_right`, 就是找到某个位置之后/之前的最近的某个字符。一种办法使用二分搜索,一个办法则是创建左右索引,这点实现差别对耗时影响还蛮大的,二分搜索大约是10420ms, 左右索引是4052ms.

use_array_index = True

if use_array_index:
    most_right = [n] * 4
    right = [[n] * 4 for _ in range(n)]
    for i in reversed(range(n)):
        x = ord(S[i]) - ord('a')
        most_right[x] = i
        right[i] = most_right.copy()

    most_left = [-1] * 4
    left = [[-1] * 4 for _ in range(n)]
    for i in range(n):
        x = ord(S[i]) - ord('a')
        most_left[x] = i
        left[i] = most_left.copy()

    def search_right(p, c):
        return right[p][c]

    def search_left(p, c):
        return left[p][c]