目录

• 题目截图
• 题目分析
• ac code
• 总结

题目截图

题目分析

• 固定了中间的数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 + 7if n < 5:return 0ans = 0d = 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, 0xycnt = 0for i in range(n):if s[i] == str(x):xcnt += 1elif s[i] == str(y):xycnt += xcntdp1[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, 0yxcnt = 0for i in range(n - 1, -1, -1):if s[i] == str(x):xcnt += 1elif s[i] == str(y):yxcnt += xcntdp2[i][10 * x + y] = yxcntfor 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 * yxans %= MODelse: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:continueif right_x[0] == i:right_x = right_x[1:]if len(left_x) == 0 or len(right_x) == 0:continuenum1 = len(left_x)num2 = len(right_x)if num1 < 2 or num2 < 2:continueelse:c1 = num1 * (num1 - 1) // 2c2 = num2 * (num2 - 1) // 2ans += c1 * c2ans %= MODreturn ans

总结

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