---
# System prepended metadata

title: 647. Palindromic Substrings
tags: [Leetcode, medium, python, c++, dynamic programming]

---

###### tags: `Leetcode` `medium` `dynamic programming` `python` `c++`

# 647. Palindromic Substrings

## [題目連結:] https://leetcode.com/problems/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:**
```
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".
```

## 解題想法:
* 此題為計算有多少個回文子字串
* 經典DP:
    * 定義dp[i][j]: **s[i]~s[j]是否為回文**
    * 則dp[i][j]為True的條件:
        * 基本最低標準: s[i]==s[j] 加上:
            * case1: 只有1個字or2個字
            * case2: 去掉左右，dp[i+1][j-1]仍為True
    * 解題思考:
        * 對於看到判斷條件i，需要用到i+1來判斷:
        * 則i迴圈為**從尾到頭**判斷，才能滿足

## Python:
``` python=
class Solution(object):
    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        #dp[i][j]: s[i]~s[j]是否為迴文
        #dp[i][j]為True的條件
        #只有一個字or兩個字
        #去掉左右，dp[i+1][j-1]仍是迴文
        res=0
        n=len(s)
        dp=[[False for _ in range(n)] for _ in range(n)]
        for i in range(n-1, -1, -1):
            for j in range(i, n):
                if s[i]==s[j]:
                    if (j-i<2) or dp[i+1][j-1]==True:
                        dp[i][j]=True
                        res+=1
        return res 
        
result= Solution()
ans=result.countSubstrings(s="aaa")
print(ans)
```

## C++:
``` cpp=
#include<bits/stdc++.h>
using namespace std;

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