陕西交通建设集团西镇分公司网站数字营销策划公司

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