Leetcode 647. 回文子串

1.题目描述

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

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

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

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

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

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

提示：

• 1 <= s.length <= 1000
• s 由小写英文字母组成

2.思路分析

2.1 动态规划

1.确定dp数组（dp table）以及下标的含义

• dp[i][j]：表示区间范围[i,j] (注意是左闭右闭)的子串是否是回文子串，如果是dp[i][j]为true，否则为false。

2.确定递推公式

• 当s[i]与s[j]不相等，dp[i][j]一定是false。
• 当s[i]与s[j]相等，有如下三种情况:
• 情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
• 情况二：下标i 与 j相差为1，例如aa，也是回文子串
• 情况三：下标：i 与 j相差大于1时，例如cabac，此时s[i]与s[j]已经相同了，判断i到j区间是不是回文子串就要看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。

3.dp数组如何初始化

• dp[i][j]初始化为false

4.确定遍历顺序

• 从下到上, 从左到右遍历

5.举例推导dp数组

• 输入：“aaa”，dp[i][j]状态如下：

2.2 中心扩展法

基于回文字符串对称性的特点，我们可以采取从中心向两边扩展的方法，得到回文子串 :

当中心是 b 时，同时向左向右扩展一格，得到的子串为 aba，仍然符合回文的性质

继续向左向右扩展一格，得到的子串不符合回文的性质，停止！！

所以：以 b 为中心，可以得到的回文子串有两个 b 和 aba

但是，仅仅以单个字母为中心的方法会遗漏掉偶数回文子串的情况，如下图所示：

ng)]

所以我们不仅需要遍历以单个字母为中心的情况，也要遍历以两个字母为中心的情况

总结：「中心扩展法」的思想就是遍历以一个字符或两个字符为中心可得到的回文子串

3.代码实现

3.1 动态规划

class Solution:
    def countSubstrings(self, s: str) -> int:
        dp = [[False] * len(s) for _ in range(len(s))]
        result = 0
        for i in range(len(s)-1, -1, -1): #注意遍历顺序
            for j in range(i, len(s)):
                if s[i] == s[j] and (j - i <= 1 or dp[i+1][j-1]): 
                    result += 1
                    dp[i][j] = True
        return result

1
2
3
4
5
6
7
8
9
10
11

复杂度分析

• 时间复杂度：O(n^2)。
• 空间复杂度：O(n^2)。

3.2 中心扩散法

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        result = 0

        def helper(s: str, i: int, j: int):
            nonlocal result
            while i >= 0 and j < n and s[i] == s[j]:
                i -= 1
                j += 1
                result += 1

        for i in range(n):
            # 以单个字母为中心的情况
            helper(s, i, i)
            # 以两个字母为中心的情况
            helper(s, i, i + 1)
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

复杂度分析

• 时间复杂度：O(n^2)。
• 空间复杂度：O(1)。

参考:https://leetcode.cn/problems/palindromic-substrings/solution/jian-dan-de-dong-tai-gui-hua-si-xiang-by-tinylife/