手机html5 网站导航代码,腾讯微博同步到wordpress,德宏网站制作,营销项目策划公司目录
力扣5. 最长回文子串
解析代码#xff08;中心拓展#xff09; 力扣5. 最长回文子串
5. 最长回文子串
难度 中等
给你一个字符串 s#xff0c;找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同#xff0c;则该字符串称为回文字符串。
示例 1#…目录
力扣5. 最长回文子串
解析代码中心拓展 力扣5. 最长回文子串
5. 最长回文子串
难度 中等
给你一个字符串 s找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同则该字符串称为回文字符串。
示例 1
输入s babad
输出bab
解释aba 同样是符合题意的答案。示例 2
输入s cbbd
输出bb提示
1 s.length 1000s 仅由数字和英文字母组成
class Solution {
public:string longestPalindrome(string s) {}
}; 解析代码中心拓展 暴力解法是ON^3对于一个子串而言如果它是回文串并且长度大于 2那么将它首尾的两个字母去除之后它仍然是个回文串。如此这样去除一直除到长度小于等于 2 时呢长度为 1 的自身与自身就构成回文而长度为 2 的就要判断这两个字符是否相等了。 从这个性质可以反推出来从回文串的中心开始往左读和往右读也是一样的。那么是否可以枚举回文串的中心呢 从中心向两边扩展如果两边的字母相同就可以继续扩展如果不同就停止扩展。这样只需要一层 for 循环就可以完成之前两层 for 循环的工作量。
class Solution {
public:string longestPalindrome(string s) {int n s.size(), begin 0, maxlen 0;for(int i 0; i n; i){int left i, right i, cnt 0; // 奇数长度拓展while(left 0 right n s[left] s[right]){--left;right;cnt right - left - 1;}if(cnt maxlen){begin left 1;maxlen cnt;}left i, right i 1, cnt 0; // 偶数长度拓展while(left 0 right n s[left] s[right]){--left;right;cnt right - left - 1;}if(cnt maxlen){begin left 1;maxlen cnt;}}return s.substr(begin, maxlen);}
};
