647. Palindromic Substrings

string

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

Example 1:

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Constraints:

• 1 <= s.length <= 1000

• s consists of lowercase English letters.

解法思路

方法一：中心扩展法

回文串可以从其中心展开，分为奇数长度和偶数长度两种情况：

1. 奇数长度：中心是一个字符（如 "aba"，中心是 'b'）。

2. 偶数长度：中心是两个相同字符（如 "abba"，中心是 'bb'）。

步骤：

1. 遍历字符串，以每个字符为中心，向左右扩展，统计以该中心的所有回文子串。

2. 对偶数长度的情况，再以当前字符和下一个字符为中心进行扩展。

时间复杂度： O(n²)，其中 n 是字符串长度。 空间复杂度： O(1)。

方法二：动态规划

定义 dp[i][j] 表示子串 s[i..j] 是否为回文串。

状态转移方程：

• 如果 s[i] == s[j]，则 dp[i][j] = dp[i+1][j-1]（即取决于内部子串）。

• 边界条件：

  • 单个字符一定是回文串（dp[i][i] = True）。

  • 两个相同字符也是回文串（dp[i][i+1] = (s[i] == s[i+1])）。

时间复杂度： O(n²)。 空间复杂度： O(n²)。

class Solution:
    def countSubstrings(self, s: str) -> int:
        res = 0
        def expand_around_center(i,j):
            nonlocal res
            while i >=0 and j < len(s) and s[i] == s[j]:
                i -= 1
                j += 1
                res += 1

        for i in range(len(s)):
            expand_around_center(i,i)
            expand_around_center(i, i + 1)
        return res