题目描述

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

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

例如：

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

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

解法

1. 暴力法

思路：遍历出所有子串，然后判断字串是否为回文子串。由于遍历所有字串需要双重循环，对每个字串检查是否为回文子串也需要一重循环。所以时间复杂度为$O(n^3)$，太高了😭

2. 动态规划

思路：一开始真没想到是动态规划🤣，看了题解评论之后才有思路的。

  • 状态划分：一个回文子串除去首尾字符，其子字符串也应该是回文子串
  • 状态确定：$dp[i][j]$表示索引为$i\ j$的字符可以构成回文子串
  • 状态转移：
  • 确定边界：单个字符本身即为一个回文子串。

注意计算方向，即i j索引代表的含义要弄清！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int countSubstrings(String s) {
        if (s.trim().equals("")) return 0;
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        int count = 0;
        for (int j = 0; j < len; j++) {
            for (int i = 0; i <= j; i++) {
                if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) {
                    count++;
                    dp[i][j] = true;
                }
            }
        }
        return count;
    }
}

时间复杂度为$O(n^2)$ 双重for循环
空间复杂度为$O(n^2)$ 使用了大小为$n^2$的额外dp空间

3. 中心扩散

思路：这种方法类似于暴力法，但是利用了回文子串的特性。字符串中每个字符都可以当作一个回文子串的中心位置，然后使用指针检查它两端的字符是否相等。问题是有可能为奇数回文子串，也有可能是偶数回文子串。奇数回文子串的中心点有一个，而偶数回文子串的中心位置有两个。这里为了好理解，就都进行计算（官方题解是寻找规律，没想清楚。。🤒）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int countSubstrings(String s) {
        if (s.trim().equals("")) return 0;
        int count = 0;
        // 遍历每个回文子串中心
        for (int i = 0; i < s.length(); i++) {
            // 奇数回文子串
            count = isPalindromic(i, i, s, count);
            // 偶数回文子串
            count = isPalindromic(i, i + 1, s, count);
        }
        return count;
    }

    private int isPalindromic(int left, int right, String s, int count) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
            count++;
        }
        return count;
    }
}

时间复杂度为$O(n^2)$ 双重for循环
空间复杂度为$O(1)$ 几个变量使用常量大小的额外dp空间

参考