最长回文子串

给定一个字符串 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），

等我看懂原理了再来更博详解。

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有