LeetCode 647：回文子串 | 中心扩展法

LeetCode 647回文子串 | 中心扩展法引言回文子串Palindromic Substrings是 LeetCode 第 647 题难度为 Medium。题目要求统计字符串中回文子串的数量。与最长回文子串不同这里需要统计所有回文子串的数量。使用中心扩展法可以在 O(n²) 时间内解决。算法实现Python 实现def countSubstrings(s): n len(s) count 0 def expandAroundCenter(left, right): nonlocal count while left 0 and right n and s[left] s[right]: count 1 left - 1 right 1 for i in range(n): expandAroundCenter(i, i) expandAroundCenter(i, i 1) return count算法详解对每个位置进行中心扩展expandAroundCenter(i, i)奇数长度回文以 i 为中心expandAroundCenter(i, i1)偶数长度回文以 i 和 i1 之间的空隙为中心复杂度分析时间复杂度O(n²)空间复杂度O(1)总结中心扩展法可以同时解决回文子串计数和最长回文子串问题。