手机网站建站系统,成都如何做网站,直接用ip做网站,评价一个网站文章目录1. 题目2. 解题2.1 动态规划2.2 中心扩展法1. 题目
给定一个字符串#xff0c;你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串#xff0c;即使是由相同的字符组成#xff0c;也会被计为是不同的子串。
示例 1:
输入: abc…
文章目录1. 题目2. 解题2.1 动态规划2.2 中心扩展法1. 题目
给定一个字符串你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串即使是由相同的字符组成也会被计为是不同的子串。
示例 1:
输入: abc
输出: 3
解释: 三个回文子串: a, b, c.示例 2:
输入: aaa
输出: 6
说明: 6个回文子串: a, a, a, aa, aa, aaa.注意:
输入的字符串长度不会超过1000。来源力扣LeetCode 链接https://leetcode-cn.com/problems/palindromic-substrings 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
参考 LeetCode 5. 最长回文子串动态规划 LeetCode 516. 最长回文子序列动态规划
2.1 动态规划
先计算长度为1,2的子串然后按长度动态规划
class Solution {
public:int countSubstrings(string s) {if(s.size() 1)return s.size();int i, j, len, n s.size(), count s.size();vectorvectorbool dp(n,vectorbool(n,0));for(i 0; i n; i){dp[i][i] true;if(i n-1 s[i]s[i1]){dp[i][i1] true;count;}}for(len 1; len n; len){for(i 0; i n-len; i){if(dp[i][ilen-1] i-10 s[i-1]s[ilen])//是回文串{dp[i-1][ilen] true;count;}}}return count;}
};124 ms 7.8 MB
2.2 中心扩展法
class Solution {
public:int countSubstrings(string s) {if(s.size() 1)return s.size();int i, count 0;for(i 0; i s.size(); i){centerspand(s,i,i,count);centerspand(s,i,i1,count);}return count;}void centerspand(string s, int l, int r, int count){while(l0 rs.size() s[l]s[r]){count;l--;r;}}
};4 ms 6.3 MB
