0730. Count Different Palindromic Subsequences ======================================================================================================================== 题目信息 -------- :题号: 0730 :难度: Hard :主题: 字符串、回文子序列、去重计数 :原题: `LeetCode 0730 `_ :重点: 统计不同的非空回文子序列字符串,相同字符序列即使由不同下标选出也只计一次;结果对 ``10^9 + 7`` 取模 题目重述 -------- 给定字符串 ``s``,统计其中可以得到多少种不同的非空回文子序列,并返回该数量对 ``10^9 + 7`` 取模后的结果。 子序列可以通过删除原字符串中的任意若干字符得到,未删除字符的相对顺序必须保持不变,不要求连续。只有正读和反读完全相同的非空子序列才算回文。计数按最终字符序列去重:同一个回文字符串即使能由多组不同下标构成,也只计一次。 ``s`` 的长度在 ``[1, 1000]`` 范围内,并且只包含字符 ``a``、``b``、``c``、``d``。 自建示例 -------- 不同下标产生相同子序列时去重: .. code-block:: text 输入:s = "aba" 输出:4 解释:不同的非空回文子序列为 "a"、"b"、"aa" 和 "aba"。字符 "a" 可从两个位置分别选出,但最终字符串相同,只计一次。 全部字符相同: .. code-block:: text 输入:s = "aaaa" 输出:4 解释:不同的回文子序列只有 "a"、"aa"、"aaa" 和 "aaaa";同一长度的多种下标选择不会增加计数。