CTF of Z2BNS
0%

动态规划

发表于
| 阅读次数： |
Valine：
本文字数： 536 阅读时长 ≈ 1 分钟

经典题型

最长回文子串

给你一个字符串s，找到s中最长的回文子串。

示例1：

1
2
3
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例2：

1
2
输入：s = "cbbd"
输出："bb"

提示：

  • 1<=s.length<=1000
  • s仅由数字和英文字母组成

代码

1

最长回文子序列

给你一个字符串s，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例1：

1
2
3
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例2：

1
2
3
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

提示

  • 1<=s.length<=1000
  • s仅由小写英文字母组成
回文子字符串的个数

给定一个字符串s，请计算这个字符串中有多少个回文子字符串

具有那个开始位置或结束位置的子串，即使是由相同的字符组成，也会被视为不同的子串。

示例1：

1
2
3
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例2：

1
2
3
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

  • 1<=s.length<=1000
  • s由小写英文字母组成
统计不同回文子序列

给定一个字符串s，返回s中不同的非空【回文子序列】个数

通过从s中删除0个或多个字符来获得子序列

如果一个字符序列与它反转后的字符序列一致，那么它是【回文字符序列】。

如果有某个i，满足ai!=bi,则两个序列a1,a2,…和b1,b2,…不同。

注意：

  • 结果可能很大，你需要对10的9次方+7取模

示例1：

1
2
3
4
输入：s = 'bccb'
输出：6
解释：6 个不同的非空回文子字符序列分别为：'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。
注意：'bcb' 虽然出现两次但仅计数一次。

示例2：

1
2
3
输入：s = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'
输出：104860361
解释：共有 3104860382 个不同的非空回文子序列，104860361 对 109 + 7 取模后的值。

提示：

  • 1<=s.length<=1000
  • s[i]仅包含’a’,’b’,’c’或’d’
------------- THE END! THANKS! -------------