算法题之回文子串

回文子串

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

示例 1：

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

示例 2：

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

提示：

• 1 <= s.length <= 1000
• s 由小写英文字母组成

解题思路

从题意可以知道，回文字符串的特点是左右两边的字符镜像对称。

我们可以遍历字符串s，然后以遍历当前的字符为中心点，比较左右两边的字符串是否相同，如果相同的话，记录答案，然后再分别向左右两边延伸继续比较，直到到达边界或者字符不相同位置。但是有个问题，就是这个方法是以字符串s的某个字符为中心的；如果是aa这样的子字符串，需要以aa中间作为中心，然后向两边延伸比较的，那怎么定位呢？

我们假设在字符串s每个字符的两侧，都插入一个特殊字符，使得我们每次遍历的时候，都可以以新的字符串中的每个字符作为中心点，这样就方便遍历了。

但是需要注意的是，由于我们插入了n + 1个特殊字符，所以遍历得到的答案是变多了的。我们需要找出得到的结果和最后结果之间的函数映射规律。

我们遍历是从原字符串的第一个字符开始，然后到最后一个节点结束：

• 原字符串是a，填充后是#a#，得到的结果是2，真实结果是1
• 原字符串是aa，填充后是#a#a#，得到的结果是7，真实结果是3
• 原字符串是aaa，填充后是#a#a#a#，得到的结果是14，真实结果是6
• 原字符串是aaaa，填充后是#a#a#a#a#，得到的结果是23，真实结果是10

 根据推断，得到的结果res和真实结果之间的规律是：

其中n是原字符串的长度。

具体的代码如下所示：

class Solution {public int countSubstrings(String s) {int n = s.length();int ans = 0;StringBuffer t = new StringBuffer("#");for (int i = 0; i < n; i++) {t.append(s.charAt(i));t.append('#');}String s2 = t.toString();n = s2.length();for (int i = 1; i < n - 1; i++) {int l = i, r = i;while (l >= 0 && r < n && s2.charAt(l) == s2.charAt(r)) {--l;++r;++ans;}}return (ans + 1 - s.length()) / 2;}
}

复杂度分析

• 时间复杂度：，遍历了一遍数组s2，并且有对比左右字符延伸的操作。
• 空间复杂度：，额外创建了一个数组s2。