Leetcode 647.回文子串

题目描述：

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

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

示例 1：

1
2
3

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

示例 2：

1
2
3

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

提示：

• 输入的字符串长度不会超过 1000 。

链接：

https://leetcode-cn.com/problems/palindromic-substrings

题目分析

  看到这道题就想到了 Leetcode 5.最长回文子串。在寻找回文子串的时候，我们其实也是对所有的回文子串进行了一次遍历。那道题我们采用的是中心扩展的算法，也就是对每一个字符都考虑其作为“回文中心”，能够扩展出多长的回文子串。
  函数 expand() 表示对回文中心 left 和 right 进行扩展，奇数时 left = right，偶数时 right = left + 1。在这里我们修改了一下函数返回值，先看看奇数的情况，比如我们以某个中心找到了最长长度为 5 的回文子串，那么长度为 1、3、5 这三个子串都是回文串。其实也就是 (len + 1) / 2。而我们长度是用最后的 right - left - 1 来获得的（最后的 left 和 right 会在最长回文串之外，也就是第一个不满足回文的字符上），那么就可以知道，回文串的数量刚好就是 (right - left) / 2。
  我们再来看看偶数的情况，比如我们找到了最长长度为 6 的回文子串，那么长度为 2、4、6 的三个子串都是回文串，也就是 len / 2，而长度同样也是 right - left - 1（这个是偶数），我们使用 (right - left) / 2 得到的也是正确的结果。这样我们函数的返回值就是该回文中心回文串的个数。
  由于回文串的中心不一样就可以肯定回文串不是同一个，那么我们直接对所有的回文中心进行寻找就可以了。这里注意一下，偶数回文中心的时候，i+1 越界有没有问题呢？如果传入函数，由于不满足 while 条件会直接返回，得到的结果是 0，是不会有问题的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    int expand(string& s, int left, int right){
        while(left >= 0 && right < s.size() && s[left] == s[right]){
            left--;
            right++;
        }
        return (right - left) / 2;
    }
public:
    int countSubstrings(string s) {
        int result = 0;
        for(int i = 0; i < s.size(); i++){
            result += expand(s, i, i);
            result += expand(s, i, i+1);
        }
        return result;
    }
};

  时间复杂度：$O(n^2)$，其中 $n$ 是字符串的长度。我们一共有 $2n-1$ 个回文中心（包括奇数和偶数），而每一次中心扩展寻找最长回文串的时间复杂度是 $O(n)$。
  空间复杂度：$O(1)$。我们只需要常数个变量的空间。