leetcode：6251. 统计回文子序列数目【dp + 统计xy子序列出现的个数】

题目截图

题目分析

• 固定了中间的数i后
• 从两边选xy 和 yx
• 对于x = y的情况，比较简单预处理每个数字出现的index为ids
• 然后看看两边x各自的个数n1 n2
• n1和n2必须大于等于2
• 左边可以选n1 * (n1 - 1) // 2
• 右边可以选n2 * (n2 - 1) // 2
• 两边乘起来即可
• 对于x ！= y的情况，要预处理前缀xy出现的个数，以及后缀xy出现的个数
• 这里需要用dp，记录着前面x出现的个数xcnt，如果当前是y，当前累计xy出现个数xycnt += xcnt即可，前缀后缀都类似处理

ac code

class Solution:
    def countPalindromes(self, s: str) -> int:
        n = len(s)
        MOD = 10 ** 9 + 7
        if n < 5:
            return 0
        ans = 0
        d = defaultdict(list)
        for i, v in enumerate(s):
            d[v].append(i)
        # dp1[i][10 * x + y]:前i个（包括第i个）xy出现的次数
        dp1 = [[0] * 100 for _ in range(n)]
        for x in range(10):
            for y in range(10):
                xcnt, ycnt = 0, 0
                xycnt = 0
                for i in range(n):
                    if s[i] == str(x):
                        xcnt += 1
                    elif s[i] == str(y):
                        xycnt += xcnt
                    dp1[i][10 * x + y] = xycnt
        # dp2[i][10 * x + y]:后i个（包括第i个）yx出现的次数
        dp2 = [[0] * 100 for _ in range(n)]
        for x in range(10):
            for y in range(10):
                xcnt, ycnt = 0, 0
                yxcnt = 0
                for i in range(n - 1, -1, -1):
                    if s[i] == str(x):
                        xcnt += 1
                    elif s[i] == str(y):
                        yxcnt += xcnt
                    dp2[i][10 * x + y] = yxcnt
                    
                    
        for i in range(2, n - 2): #i作为分割点
            # s[:i] and s[i + 1:]
            for x in range(10):
                for y in range(10):
                    # xy + yx是否能出现
                    x, y = str(x), str(y)
                    xs, ys = d[x], d[y]
                    if len(xs) == 0 or len(ys) == 0:
                        continue

                    # print(x, y, i)
                    # print(left_x, right_x)
                    # print(left_y, right_y)
                    if x != y:
                        # [:i] xy出现的个数
                        # [i + 1:] yx出现的个数
                        # 能否预处理
                        xy, yx = dp1[i - 1][10 * int(x) + int(y)], dp2[i + 1][10 * int(x) + int(y)]
                        # print(xy, yx)
                        ans += xy * yx
                        ans %= MOD
                    else:
                        idx_x = bisect_left(xs, i)
                        left_x, right_x = xs[:idx_x], xs[idx_x:]
                        if len(left_x) == 0 or len(right_x) == 0:
                            continue
                        if right_x[0] == i:
                            right_x = right_x[1:]
                        if len(left_x) == 0 or len(right_x) == 0:
                            continue
                        num1 = len(left_x)
                        num2 = len(right_x)
                        if num1 < 2 or num2 < 2:
                            continue
                        else:
                            c1 = num1 * (num1 - 1) // 2
                            c2 = num2 * (num2 - 1) // 2
                            ans += c1 * c2
                            ans %= MOD
        return ans
                    
        
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

总结

• 一开始以为是模板，后面自己慢慢优化出来了
• 先固定中间无关紧要的
• 两边必定是xy以及yx
• xy相同or不相同
• x和y只有10个取值
• 预处理前缀和后缀中xy出现的个数即可
• 本质还是累计x出现的个数即可，动态规划