647. 回文子串（leetcode）

647. 回文子串（leetcode）

题目描述

给你一个字符串 s ，请你统计并返回这个字符串中回文子串的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。

示例1

输入：s = “abc”
输出：3
解释：三个回文子串: “a”, “b”, “c”

示例2

输入：s = “aaa”
输出：6
解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

提示信息

1 <= s.length <= 1000
s 由小写英文字母组成

题解1（C++版本）

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        bool dp[n + 1][n + 1]; // dp[i][j] = true 表示区间[i,j]这部分子串是回文子串
        int ans = 0;
        memset(dp, 0, sizeof dp);
        for(int i = 1; i <= n; i++) {
            dp[i][i] = 1;
            ans++;
        }
        for(int i = 1; i < n; i++){
            if(s[i - 1] == s[i]){
                dp[i][i + 1] = 1;
                ans++;
            }
        }
        for(int len = 3; len <= n; len++){
            for(int i = 1; i + len - 1 <= n; i++){
                int j = i + len - 1;
                if(s[i - 1] == s[j - 1] && dp[i + 1][j - 1] == true){
                    dp[i][j] = true;
                    ans++;
                }
            }
        }

        return ans;
    }
};