给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 长度最长为1000。
示例:
输入: "babad" 输出: "bab" 注意: "aba"也是有效答案
示例:
输入: "cbbd" 输出: "bb"
哎，看到这个题目深感痛苦，华为笔试第一题就是这题，只不过是返回最大长度，
然后不会做，心疼。
然后在leetcode找到了这道题，从而发誓要把LeetCode每一道题刷完。
暴力解法，这个容易理解，从头开始遍历字符串，每遇到一个字符，就从该
字符开始前后判断是否是回文字符串，奇数长度则该字符为中心，偶数长度
就是该字符和下一个字符为中心。
时间复杂度O（n2）
class Solution {
public:
string longestPalindrome(string s) {
if(s=="") return "";
int max=1;
string a="";
string res="";
for(int i=0;i<s.size();i++)
{
a="";
int x=i-1;
int y=i+1;
int length=1;
a=a+s[i];
while(x>-1&&y<s.size()) //这个方法有点笨，先判断是奇数情况
{
if(s[x]==s[y])
{
a=s[x]+a+s[y];
x--;
y++;
length+=2;
}
else break;
}
if(length>=max)
{
res=a;
max=length;
}
}
for(int i=0;i<s.size();i++)
{
a="";
int x=i;
int y=i+1;
int length=0;
while(x>-1&&y<s.size()) //后判断是偶数情况
{
if(s[x]==s[y])
{
a=s[x]+a+s[y];
x--;
y++;
length+=2;
}
else break;
}
if(length>max)
{
res=a;
max=length;
}
}
return res;
}
};
上面这个暴力解法，果然94个样例用了1196ms，明显时间复杂度过高。
优化解法
试想，一个字符串是回文字符串，那个有可能是abba，或者abcba情况，
尝试用一个循环解决问题，先判断其是否是第一种情况(即是是否有连续重复字符，有则其肯定是回文字符串子串)，
然后假设不符合上一情况后，再判断第二种情况，即可减少循环次数。
class Solution {
public:
string longestPalindrome(string s) {
if(s=="") return "";
if(s.size()==1) return s;
int len=1;
int min=0;
for(int i=0;i<s.size();)
{
if(s.size()-i<=len/2) break; //如果剩下的字符串长度都少于或等于len的一半，不用判断了，len肯定为最长了
int l=i;
int r=i;
while(r<s.size()-1 && s[r]==s[r+1]) r++; //判断连续重复字符，有多少个重复字符长度就增长多少
i=r+1; //不符合连续重复字符后，由r位置定位i，并且s[r]肯定不等于s[r+1]了，则可以判断s[r+1]与s[l-1]的关系了
while(r<s.size()-1 && l>0 && s[r+1]==s[l-1])
{
r++; //扩展
l--;
}
if(r-l+1>len) //判断
{
min=l; //min定位最长回文字符串开头
len=r-l+1;
}
}
return s.substr(min,len);
}
};
然后提交4ms过了全部样例，当是优化了吧。
还有一个后缀树是解决这类字符串问题的极佳方法，可以把时间复杂度降为O（n），
等我看懂原理了再来更博详解。
如对本文有疑问， 点击进行留言回复！！
qdockwidget 显示问题，图标问题，标题栏问题，拖动、分隔线问题
Qt编译出现QObject::connect: Cannot queue arguments of type 【解决方法】
Qt项目中，用QPainter进行绘制图形时，边角显示不完整问题的梳理
我要评论
网友评论