給你一個字符串 s ，請你統計并返回這個字符串中 回文子串 的數目。

回文字符串 是正著讀和倒過來讀一樣的字符串。

子字符串 是字符串中的由連續字符組成的一個序列。

具有不同開始位置或結束位置的子串，即使是由相同的字符組成，也會被視作不同的子串。

示例 1：

輸入：s = “abc”
輸出：3
解釋：三個回文子串: “a”, “b”, “c”
示例 2：

輸入：s = “aaa”
輸出：6
解釋：6個回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

提示：

1 <= s.length <= 1000
s 由小寫英文字母組成

ACcode

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

注意的點：

1. 遍歷順序 自底向上，從左到右
2. 初始化為false
3. j-i<=1這種情況，表示邊界，子串的數量分別是1和2
4. 整個循環內部基于s[i] == s[j]進行討論！即首尾相等的情況下討論。
5. 布爾類型的dp[i][j]：表示區間范圍[i,j] （注意是左閉右閉）的子串是否是回文子串，如果是dp[i][j]為true，否則為false。