首页 > 代码库 > [Leetcode] Longest palindromic substring 最长回文子串

[Leetcode] Longest palindromic substring 最长回文子串

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

做这道题之前要先了解什么是回文子串。回文串通俗的解释是,分别从字符串两端开始遍历,得到的结果相同,如“abba”,从两端的遍历结果都是:“abba”。

判断一个字符串是否为回文串的思路是使用两个指针从,两端开始向中间遍历,看是否对应的字符是否相等,直到两指针相等或者交叉。

方法一:以字符串中的每一个字符为中心遍历字符串。

思路:本题的解决方法是从头到尾的遍历字符串S,以每个字符为中心,向两端不停的扩展,同时判断以当前字符为中心的两端字符是否相等,在判断的过程中找到最大的回文串长度,并记录下回文串开始的最左端,这样就找到了最大的回文串。但是这样做就遇到了一个问题:“abcab”这种个数为奇数的回文串可以计算出来,但是若是"abba"这样个数为偶数的情况,该如何计算?遇到这种情况,则,可以判断相邻两字符是否相等来判断是否为回文串,针对s=“abba”,我们发现 i=1时,s[i]==s[i+1],然后同时向两端扩,发现s[ 0]=s[ 2],这样该串也为回文串,所以,在判断以某字符为中心的时候,要分两种情况,即,回文串中字符的个数为奇数和为偶数的情况。时间复杂度是O(n*n)。代码如下:

 1 class Solution {
 2 public:
 3     string longestPalindrome(string s) 
 4     {
 5         string res="";
 6         int len=s.size();
 7         if(len==1)  return s;
 8         int maxLen=0,curLen=0,sbegin;
 9 
10         for(int i=0;i<len;++i)
11         {
12             //奇数
13             int left=i-1,right=i+1;
14             while(left>=0&&right<len&&s[left]==s[right])
15             {
16                 curLen=right-left;
17                 if(curLen>maxLen)
18                 {
19                     maxLen=curLen;
20                     sbegin=left;
21                 }
22                 left--,right++;
23             }
24 
25             //偶数
26             left=i,right=i+1;
27             while(left>=0&&right<len&&s[left]==s[right])
28             {
29                 curLen=right-left;
30                 if(curLen>maxLen)
31                 {
32                     maxLen=curLen;
33                     sbegin=left;
34                 }
35                 left--,right++;
36             }
37         }
38         res=s.substr(sbegin,maxLen+1);  //substring()为前闭后开
39         return res;
40     }
41 };

 

方法二:马拉车算法Manacher‘s Algorithm,有点是:将时间复杂度降低为O(n)的地步。关于马拉车算法Manacher‘s Algorithm,详情见博客Manacher‘s Algorithm详解。

 

[Leetcode] Longest palindromic substring 最长回文子串