LeetCode 647：回文子串 — 逐步可视化追踪

Source: Dev.to

问题描述

计算给定字符串中回文子串的总数，回文子串是指正读和反读都相同的子串。

方法

使用中心扩展技术，检查字符串中的每一个可能的中心位置。对每个位置向两侧展开，只要字符相同就计数，以此统计奇数长度和偶数长度的回文子串。

复杂度

• 时间复杂度: O(n²)
• 空间复杂度: O(1)

解法

class Solution:
    def countSubstrings(self, s: str) -> int:
        def expandAroundCenter(left: int, right: int) -> int:
            count = 0
            # Expand around the center while the characters at both ends are equal.
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
                count += 1
            return count

        if not s:
            return 0

        total_palindromes = 0

        for i in range(len(s)):
            # Check for odd-length palindromes.
            total_palindromes += expandAroundCenter(i, i)

            # Check for even-length palindromes.
            total_palindromes += expandAroundCenter(i, i + 1)

        return total_palindromes