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.

求字符串里的最长回文段。

注意下标的运动。区分奇偶待选回文字段。

 1 class Solution {
 2 public:
 3     string longestPalindrome(string s) {
 4         int n=s.size();
 5         if(n<2) return s;
 6         if(n==2&&(s[0]==s[1])) return s;
 7         
 8         int maxlength=0;
 9         int left=0;
10         int right=0;
11         string res;
12         for(int i=0;i<n-1;i++)
13         {
14             if(s[i]!=s[i+1]&&s[i]!=s[i+2])
15                 continue;
16             if(s[i]==s[i+1])
17             {
18                 left=i;
19                 right=i+1;
20             
21             
22                 while(left>0&&right<n-1)           
23                 {
24                     if(s[left-1]==s[right+1])
25                     {
26                         left--;
27                         right++;
28                         continue;
29                     }
30                     break;
31                 }
32                 int tmplength=right-left+1;
33                 if(tmplength>maxlength)
34                 {
35                     res=s.substr(left,tmplength);
36                     maxlength=tmplength;
37                 }
38             }
39             if(i+2<n&&s[i]==s[i+2])
40             {
41                 left=right=i+1;
42             
43                 while(left>0&&right<n-1)         //注意边界选取，若采用s[left]==s[right],则会出现abcbe res=abcbe的情况。
44                 {
45                     if(s[left-1]==s[right+1])
46                     {
47                         left--;
48                         right++;
49                         continue;
50                     }
51                     
52                     break;
53                 }
54                 int tmplength=right-left+1;
55                 if(tmplength>maxlength)
56                 {
57                     res=s.substr(left,tmplength);
58                     maxlength=tmplength;
59                 }
60             }
61         }
62         
63        
64         return res;
65     }
66 };

新的写法

class Solution {
public:
    string longestPalindrome(string s) {
        string res = s;
        if(s.size()<2) return res;
        int l=0,r=1;
        int max=0;
        for(int i=0;i<s.size()-1;++i)
        {
            isPa(s,i,i,l,max);
            isPa(s,i,i+1,l,max);
        }
        return s.substr(l,max);
    }
    void isPa(string s, int l, int r, int &start, int &max)
    {
        while(l>=0&&r<s.size()&&s[l]==s[r])
        {
            l--;
            r++;
        }
        if(r-l-1>max)
        {
            start=l+1;
            max=r-l-1;
        }
    }
};

我们知道传统的验证回文串的方法就是两个两个的对称验证是否相等，那么对于找回文字串的问题，就要以每一个字符为中心，像两边扩散来寻找回文串，这个算法的时间复杂度是 O(n*n)，可以通过 OJ，就是要注意奇偶情况，由于回文串的长度可奇可偶，比如 "bob" 是奇数形式的回文，"noon" 就是偶数形式的回文，两种形式的回文都要搜索，对于奇数形式的，我们就从遍历到的位置为中心，向两边进行扩散，对于偶数情况，我们就把当前位置和下一个位置当作偶数行回文的最中间两个字符，然后向两边进行搜索。

注意搜索的时候，出while循环时l与r肯定不相等，因此是r-l-1,start=l+1