【力扣】647.回文子串

问题描述

思路解析

中心扩展法
这是一个比较巧妙的方法，实质的思路和动态规划的思路类似。

比如对一个字符串 ababa，选择最中间的 a 作为中心点，往两边扩散，第一次扩散发现 left 指向的是 b，right 指向的也是 b，所以是回文串，继续扩散，同理 ababa 也是回文串。

这个是确定了一个中心点后的寻找的路径，然后我们只要寻找到所有的中心点，问题就解决了。

中心点一共有多少个呢？看起来像是和字符串长度相等，但你会发现，如果是这样，上面的例子永远也搜不到 abab，想象一下单个字符的哪个中心点扩展可以得到这个子串？似乎不可能。所以中心点不能只有单个字符构成，还要包括两个字符，比如上面这个子串 abab，就可以有中心点 ba 扩展一次得到，

所以最终的中心点由 2 * len - 1 个，分别是 len 个单字符和 len - 1 个双字符。

如果上面看不太懂的话，还可以看看下面几个问题：

为什么有 2 * len - 1 个中心点？
aba 有5个中心点，分别是 a、b、c、ab、ba
abba 有7个中心点，分别是 a、b、b、a、ab、bb、ba
什么是中心点？
中心点即 left 指针和 right 指针初始化指向的地方，可能是一个也可能是两个
为什么不可能是三个或者更多？
因为 3 个可以由 1 个扩展一次得到，4 个可以由两个扩展一次得到

代码

class Solution {public int countSubstrings(String s) {int result = 0;for (int i = 0; i < s.length(); ++i) {// Odd length palindromes, with center at index iresult += extendPalindrome(s, i, i);// Even length palindromes, with centers at indices i and i+1result += extendPalindrome(s, i, i + 1);}return result;}private int extendPalindrome(String s, int left, int right) {int count = 0;while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {--left;++right;++count;}return count;}
}