做交易网站需要多少钱,如何编写网站建设,做网站哪家公司好,建设银行个人网上银行登录入口文章目录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
