题目

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

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

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

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= s.length <= 1000

  • s 由小写英文字母组成

    解题方法

    动态规划

    设定动态数组dp[i][j]表示下标i至j的字符是否回文，则有如下递推关系：
    647. 回文子串 - 图1
    时间复杂度O(n^2)，空间复杂度O(n)。
    C++代码：

    1. class Solution {
    2. public:
    3.   int countSubstrings(string s) {
    4.       int size = s.size();
    5.       vector<bool> dp(size, false);
    6.       int result = 0;
    7.       for(int i=size-1; i>=0; i--) {
    8.           for(int j=size-1; j>=i; j--) {
    9.               if(s[i]==s[j] && (j-i<=1 || dp[j-1])) {
    10.                   result++;
    11.                   dp[j] = true;
    12.               }
    13.               else dp[j] = false;
    14.           }
    15.       }
    16.       return result;
    17.   }
    18. };

    双指针

    设定双指针，从中心向外扩展寻找回文串，遍历所有可能的中心（单点中心，两点中心）
    时间复杂度O(n^2)，空间复杂度O(1)。
    C++代码：

    class Solution {
public:
  int extent(string& s, int l, int r) {
      int result = 0;
      while(l>=0 && r<s.size() && s[l]==s[r]) {
          result++;
          l--;
          r++;
      }
      return result;
  }

  int countSubstrings(string s) {
      int result = 0;
      for(int i=0; i<s.size(); i++) {
          result += extent(s, i, i);
          result += extent(s, i, i+1);
      }
      return result;
  }
};

    Manacher 算法

    该算法可以在O(n)时间内求解最长回文长度。
    将字符串用'*'分隔，再在头尾添加不同的符合表示开头和结尾，如'$'和'@'。
    遍历每个字符将之作为中心，维护当前回文串的最右端点rmax以及对应的中心索引imax，并记录当前中心的回文半径f[i]。

f[i]的初始化方式如下所示：

  • i>rmax：将f[i]初始化为1。
  • i≤rmax：则f[i]至少为f[2*imax-i]或rmax-i+1，取最小值（先保证在最大回文串内，再向外扩展）。

image.png
随后扩展f[i]直至t[i+f[i]]≠t[i-f[i]]。此时根据f[i]为当前中心的回文半径，由于字符串由原字符串和'*'穿插组成，所以f[i]/2表示当前中心能够形成的回文串数目，累加即总的回文串数目。
时间复杂度O(n)，空间复杂度O(n)。
C++代码：

class Solution {
public:
    int countSubstrings(string s) {
        string t = "$*";
        for(char ch : s) {
            t+= ch;
            t+= '*';
        }
        int size = t.size();
        t += '@';
        cout<<t<<endl;

        vector<int> f(size, 0);
        int rmax = 0;
        int imax = 0;
        int result = 0;
        for(int i=1; i<size; i++) {
            f[i] = i<=rmax ? min((rmax-i+1), f[2*imax-i]) : 1;
            while(t[i+f[i]]==t[i-f[i]]) f[i]++;
            if(f[i]+i-1>rmax) {
                rmax = f[i] + i -1;
                imax = i;
            }
            result += f[i]/2;
        }
        return result;
    }
};