# 647. Palindromic Substrings

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:**

<pre><code><strong>Input: s = "abc"
</strong><strong>Output: 3
</strong><strong>Explanation: Three palindromic strings: "a", "b", "c".
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: s = "aaa"
</strong><strong>Output: 6
</strong><strong>Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
</strong></code></pre>

&#x20;

**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²)。

```python3
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


```