剑指 Offer II 020. 回文子字符串的个数

作者：天景科技苑 | 2024-07-08 17:52:30

踩

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

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

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

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

对于一个子串而言，如果它是回文串，并且长度大于 2 , 那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串 “ababa”, 如果我们已经知道 “bab" 是回文串，那么 "ababa"一定是回文串，这是因为它的首尾两个字母都是 “a”。

根据这样的思路，我们就可以用动态规划的方法解决本题。

第 1 步：定义状态

我们用

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/天景科技苑/article/detail/799600