描述


给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例

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

提示

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

    解题思路

1. 动态规划法

  • 状态：dp[i][j] 表示字符串s在[i,j]区间的子串是否是一个回文串。
  • 状态转移方程：当 s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1]) 时，dp[i][j]=true，否则为false

代码

  1. class Solution {
  2.     public int countSubstrings(String s) {
  3.         //动态规划法
  4.         int n = s.length();
  5.         int ans = 0;
  6.         boolean dp[][] = new boolean[n][n];
  7.         for (int j = 0; j < n; j++) {
  8.             for (int i = 0; i <= j; i++) {
  9.                 if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) {
  10.                     dp[i][j] = true;
  11.                     ans++;
  12.                 }
  13.             }
  14.         }
  15.         return ans;  
  16.     }
  17. }

2.中心扩展法

  • 枚举每一个可能的回文中心，然后用两个指针分别向左右两边拓展，当两个指针指向的元素相同的时候就拓展，否则停止拓展。
  • 在实现的时候，我们需要处理一个问题，即如何有序地枚举所有可能的回文中心，我们需要考虑回文长度是奇数和回文长度是偶数的两种情况。如果回文长度是奇数，那么回文中心是一个字符；如果回文长度是偶数，那么中心是两个字符。
  • 我们不妨写一组出来观察观察，假设 n = 4，我们可以把可能的回文中心列出来：
编号 i 回文中心左起始位置 l**i** 回文中心右起始位置 r**i**
0 0 0
1 0 1
2 1 1
3 1 2
4 2 2
5 2 3
6 3 3

由此我们可以看出长度为 n 的字符串会生成 2n - 1 组回文中心 [li, ri], 其中 li = ⌊i/2⌋, ri = li + (i mod 2)。
这样我们只要从 0 到 2n - 2遍历 i，就可以得到所有可能的回文中心，这样就把奇数长度和偶数长度两种情况统一起来了。

代码

class Solution {
    public int countSubstrings(String s) {
        int n = s.length(), ans = 0;
        for (int i = 0; i < 2 * n - 1; ++i) {
            int l = i / 2, r = i / 2 + i % 2;
            while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
                --l;
                ++r;
                ++ans;
            }
        }
        return ans;
    }
}

3.中心扩展法(更新)

第一种中心扩展法并不好想，这里更新一下我自己的想法：

  • 中心扩展法其实也是先进行一次遍历，对里面的每个元素，统计以它们为中心的回文的个数。
  • 里面比较难处理的部分其实是，回文串长度可能是奇数，也可能是偶数。奇数比较好处理，对于偶数，回文中心一定是两个相同的字符，所以我们在遍历时，如果坐标 i + 1 的字符与 i 位置的字符相同，就还要统计以它们两为中心的回文串个数。
  • 因此，我们可以将判断回文的函数提出来，并且在参数里传左右指针的位置

代码

class Solution {
    private int len;
    public int countSubstrings(String s) {
        len = s.length();
        int ans = 0;
        for (int i = 0; i < len - 1; i++) {
            ans += countByIndex(s, i - 1, i + 1);
            if (s.charAt(i) == s.charAt(i + 1)) {
                ans += countByIndex(s, i - 1, i + 2);
            }
        }
        ans++;
        return ans;
    }
    public int countByIndex(String s, int left, int right) {
        int res = 1; // 自身也是回文
        while (left >= 0 && right < len) { // 保证不越界
            if (!(s.charAt(left) == s.charAt(right))) {
                break;
            }
            res++;
            left--;
            right++;
        }
        return res;
    }
}