重庆建设行业信息网站,google搜索优化,类网站建设,最新国际新闻事件题目描述
给你一个字符串 s #xff0c;请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串#xff0c;即使是由相同的字符组成#xff0c…题目描述
给你一个字符串 s 请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串即使是由相同的字符组成也会被视作不同的子串。
示例 1
输入s abc
输出3
解释三个回文子串: a, b, c示例 2
输入s aaa
输出6
解释6个回文子串: a, a, a, aa, aa, aaa提示
1 s.length 1000s 由小写英文字母组成
解答
class Solution {
public:int countSubstrings(string s) {// 这里dp数组是二维的因为要记录开始的信息才能往后判断回文// dp[i][j] 表示 在区间[i, j]的子串是否是回文子串若是为true否则为false// 当s[i] ! s[j]时 dp[i][j] false;// 当s[i] s[j]时有如下三种情况// 1.下标i 和j同 即同一个字符则为true// 2.下标 i 和 j相差1如 aa也是true// 3.下标 i 和 j相差大于1时就是考察dp[i 1][j - 1]是否为true若是则dp[i][j] true,否则 dp[i][j] falseint len s.size();vectorvectorbool dp(len, vectorbool(len, false));// dp[i 1][j - 1] 在dp[i][j] 的左下角所以遍历顺序是从上到下从左到右int res 0;for(int i len - 1; i 0; i--){for(int j i; j len; j){if(s[i] s[j]){if(j - i 1 || dp[i 1][j - 1]){res;dp[i][j] true;}}}}return res;}
};
