LeetCode/solutions/647. Palindromic Substrings.md

# [647. Palindromic Substrings](https://leetcode.com/problems/palindromic-substrings/)

# 思路
计算有多少个回文子串。

## 思路一、扩散法

根据回文串的定义，回文串是对称的。所以我们可以以字符串中的每个字符作为回文串中心位置，然后向两边扩散，每当成功匹配两个左右两个字符，就说明找到了一个回文串，res自增1。注意回文字符串有奇数和偶数两种形式，处理方式略有不同。

空间复杂度O(1)， 时间复杂度O(n^2)

## 思路二、动态规划

还可以用动归来做：
```
dp[i][j] (i <= j) 定义成子字符串s[i,...,j]是否是回文串
```
所以初始状态就是`dp[i][i] = true`，状态转移方程为：
```
if s[i] == s[j] && (i+1 == j || dp[i+1][j-1]) :
    dp[i][j] = true
```

空间复杂度O(n^2)， 时间复杂度O(n^2)，亲测比思路一慢不少

# C++
## 思路一
``` C++
class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size(), res = 0;
        
        for(int i = 0; i < n; i++){
            // 奇
            for(int j = 0; j <= min(i, n - 1 - i); j++){
                if(s[i-j] == s[i+j]) res++;
                else break;
            }
            // 偶
            for(int j = 1; j <= min(i+1, n - 1 - i); j++){
                if(s[i-j+1] == s[i+j]) res++;
                else break;
            }
        }
        return res;
    }
};
```

## 思路二
``` C++
class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size(), res = 0;
        
        vector<vector<bool>>dp(n, vector<bool>(n, false));
        for(int i = n - 1; i >= 0; i--)
            for(int j = n - 1; j >= i; j--){
                if(s[i] == s[j] && (i == j || i+1 == j || dp[i+1][j-1])){
                    dp[i][j] = true;
                    res++;
                }
            }
        return res;
    }
};
```