******** 剑指 Offer II 020. 回文子字符串的个数

题目难度: 中等

原题链接

今天继续更新 Leetcode 的剑指 Offer（专项突击版）系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。

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

示例 1：

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

示例 2：

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

提示：

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

题目思考

1. 如何尽可能优化时间复杂度?

解决方案

思路

• 分析题目, 最容易想到的做法是枚举每个子字符串的起点和终点(O(N^2)), 然后利用双指针, 判断该子字符串是否是回文(O(N))
• 但这样时间复杂度达到了 O(N^3), 效率比较低, 如何优化呢?
• 我们可以反其道而行之, 注意到每个回文子串的中心只有两种情况:
  1. 子串长度为奇数, 中心为单个字符
  2. 子串长度为偶数, 中心为最中间两个字符的中间
• 我们可以枚举每个中心, 即每个下标 i 的[i,i]和[i,i+1](不包含最后一个下标)
• 然后利用双指针, 向两边扩散, 比较当前字符是否相等:
  • 相等, 则找到一个新的回文子串, 计入总数, 继续向两边扩散
  • 不相等, 则更长的子串更不可能回文, 直接跳出循环
• 总之就是将原有的判断回文的双指针向中心收敛的过程, 变成了从中心向两边扩散的过程
• 这样外层循环和内层循环都是 O(N)时间复杂度, 总时间复杂度就优化到了 O(N^2)
• 下面代码有详细的注释, 方便大家理解

复杂度

• 时间复杂度 O(N^2): 外层循环 O(N)遍历扩散中心, 内层循环 O(N)进行中心扩散, 共计 O(N^2)
• 空间复杂度 O(1): 只使用了几个常数空间的变量

代码

class Solution:
    def countSubstrings(self, s: str) -> int:
        # 中心扩散求回文子串
        n = len(s)
        res = 0

        def getCount(l, r):
            # 以[l,r]为中心, 向两边扩散, 直到不满足回文为止
            # cnt是以[l,r]为中心的回文子串个数
            cnt = 0
            while l >= 0 and r < n and s[l] == s[r]:
                cnt += 1
                l -= 1
                r += 1
            return cnt

        for i in range(n):
            # 对于下标i, 扩散中心可以是[i,i]或者[i,i+1] (i+1<n)
            res += getCount(i, i) + getCount(i, i + 1)
        return res

大家可以在下面这些地方找到我~😊

我的 GitHub

***********

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊