回文子串
Palindromic Substrings
题目详情
问题：回文子串
考察：字符串、动态规划、双指针
来源：Citadel
链接：https://www.jointaro.com/interviews/questions/palindromic-substrings/
Given a string s, return the number of palindromic substrings in it.
A string is a palindrome when it reads the same backward as forward.
A substring is a contiguous sequence of characters within the string.
Example 1:
Input: s = "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c".
Example 2:
Input: s = "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
Constraints:
1 <= s.length <= 1000sconsists of lowercase English letters.
解析
思路：枚举每个回文中心，包括字符中心和字符间中心，向两边扩展，只要两端相等就计数。
复杂度：时间 O(n^2)，空间 O(1)。