【Leetcode Daily】1930长度为3的不同回文子序列

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个字符串，找出其中所有的不同的回文子序列，这些子序列要求长度为 3，回文是正序和倒序内容一致，子序列是由原序列删除字符组成。

思路分享

• 基本的枚举思路可以参考【Leetcode Daily】2909元素和最小的山形三元组。

• 通过基本思路可知，可以分别用哈希表处理中间下标的左侧与右侧，剩下的内容在于如何对三元组去重（题目要求不同），大致可以分成三种。

• 第一种，采用 set 或者直接存储字符串的哈希表来去重，顾名思义，只要确保对应字符串的唯一，当然可以实现记录不同的回文字符串。

• 第二种，采用二维数组，由于第一位和第三位的字母相同，所以可以让中间的字母一维，另外的字母放二维，这样的二维数组执行效率大大高于第一种方法。

• 第三种，采用位运算去重，就是在第二种方法上，通过位运算去掉二维，具体是这样实现的。已知字母无非就26位，那么对于每一个中间字母的情况，下面都算是有 26 个分支情况，方法二另开的26个位置放值 1 或 0，但这些位置仍然算整数（如果不是 Python，就能直接说算 4 字节，但 Python 是动态），比单个位要大。如果每一个字母，用一个长度为 26 位的二进制数来表示，空间占用定会大大减小。

  https://leetcode.cn/problems/unique-length-3-palindromic-subsequences/solutions/869697/mei-ju-zhong-jian-zi-fu-ran-hou-gen-ju-q-186d/comments/2471709/

代码解答（强烈建议自行解答后再看）

• 参考题解

# 解法三，巧用位运算
class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        suf = Counter(s)
        pre = defaultdict(int)
        rec = [0 for _ in range(0, 26)] # 一维数组，初始 0
        for c in s:
            suf[c] -= 1
            for letter in range(97, 123):
                tmp = chr(letter)
                if pre[tmp] and suf[tmp]:
                    rec[ord(c)-ord('a')] |= (1 << (letter - ord('a')))
            pre[c] += 1

        ans = 0
        for mask in rec:
            ans += bin(mask).count('1')
        return ans

# 解法二，通过二维数组去重
# class Solution:
#     def countPalindromicSubsequence(self, s: str) -> int:
#         suf = Counter(s)
#         pre = defaultdict(int)
#         rec = [[0 for _ in range(0, 26)] for _ in range(0, 26)] # 二维数组，初始 0
#         ans = 0
#         for c in s:
#             suf[c] -= 1
#             for letter in range(97, 123):
#                 tmp = chr(letter)
#                 if pre[tmp] and suf[tmp] and rec[ord(c)-ord('a')][letter - ord('a')] == 0:
#                     ans += 1
#                     rec[ord(c)-ord('a')][letter - ord('a')] += 1
#             pre[c] += 1

#         return ans

# 解法一，通过 set 或者其它去重方法实现
# class Solution:
#     def countPalindromicSubsequence(self, s: str) -> int:
#         suf = Counter(s)
#         pre = defaultdict(int)
#         rec = defaultdict(int)
#         ans = 0
#         for c in s:
#             suf[c] -= 1
#             for letter in range(97, 123):
#                 tmp = chr(letter)
#                 if pre[tmp] * suf[tmp] > 0 and rec[tmp + c + tmp] == 0:
#                     ans += 1
#                     rec[tmp + c + tmp] += 1
#             pre[c] += 1

#         return ans