网站建设方案范文8篇,天津网站建设哪家做得好,网站被qq拦截 做301,网站做兼容需要多少钱文章目录 LeetCode647#xff1a;回文子串题目示例提示解题思路解题代码复杂度 LeetCode5:最长回文子串题目示例提示解题思路解题代码复杂度 总结 LeetCode647#xff1a;回文子串
题目
给你一个字符串 s #xff0c;请你统计并返回这个字符串中 回文子串 的数目。
回文字… 文章目录 LeetCode647回文子串题目示例提示解题思路解题代码复杂度 LeetCode5:最长回文子串题目示例提示解题思路解题代码复杂度 总结 LeetCode647回文子串
题目
给你一个字符串 s 请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串即使是由相同的字符组成也会被视作不同的子串。示例
输入s abc
输出3
解释三个回文子串: a, b, c输入s aaa
输出6
解释6个回文子串: a, a, a, aa, aa, aaa提示
1 s.length 1000s 由小写英文字母组成
解题思路
回文字符串的概念已经明白回文字符串的长度分为两种奇数偶数。
如果字符串奇数的话就是不需要考虑中间的字符从中间向两边扩展若左边等于右边则为回文字符直到左边字符不等于右边字符或到达边界停止比如 aba。如果字符串长度偶数的话取最中间的两值向两边扩展若左边等于右边则为回文字符直到左边字符不等于右边字符或到达边界停止比如 abba。 所以我们需要遍历一遍字符串对当前字符串下标有两种选择一种当成字符串长度为奇数去向两边扩展一种是当成长度为偶数去向两边扩展。
解题代码
class Solution {
public:int countSubstrings(string s) {int cnt 0;for(int i 0;i s.size(); i){cnt excend(s, i, i, s.size());cnt excend(s, i, i1, s.size());}return cnt;}int excend(string s, int i,int j,int n){int cnt 0;while(i 0 j n s[i] s[j]){i--;j;cnt;}return cnt;}
};复杂度
时间复杂度O(n^2)空间复杂度O(1)
LeetCode5:最长回文子串
题目
给你一个字符串 s找到 s 中最长的回文子串。如果字符串的反序与原始字符串相同则该字符串称为回文字符串。示例
输入s babad
输出bab
解释aba 同样是符合题意的答案。输入s cbbd
输出bb提示
1 s.length 1000s 仅由数字和英文字母组成
解题思路
有了上一道题的基础这道题写的就游刃有余了一开始想着可以讲所有回文字符串存放到一个数组中但是截取字符串时间复杂度为ON可能会超时就用两个数据left、right代替回文字符串的左右端如果新的回文子串长度大于right - left的长度更新left、right。
解题代码
class Solution {int left 0;int right 0;
public:string longestPalindrome(string s) {for(int i 0 ;i s.size();i){excend(s,i,i,s.size());excend(s,i,i1,s.size());}return s.substr(left,right-left1);}void excend(string s, int i,int j,int n){int cnt 0;while(i 0 j n s[i] s[j]){if(j - i right - left){right j;left i;}i--;j;}}
};复杂度
时间复杂度O(n^2)空间复杂度O(1)
总结
做了第一道题回文子串再写最长回文子串更简单这种题还有一种dp写法在这里就不描述了。
更多资料点击 GitHub 欢迎各位读者去Star
⭐学术交流群Q 754410389 持续更新中~~~
