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

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

#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;
    }
};