[LeetCode] Longest Palindromic Substring 最长回文串

比较好的办法暂时没想到，这里想到的是最傻的遍历的办法，找到一个字符，然后向两边遍历的方式，时间复杂度是O（n*n），是可以AC的，主要是因为题目限定了最长的输入字符串是1000。思路很简单，就是找类似于toot或者mum的字符串，但是不能过所有的测试用例，后来发现存在一种类似于ccc的串，因此又加了一层判断。

通过的代码如下：

 1 class Solution {
 2 public:
 3     string longestPalindrome(string s) {
 4         if(s.length() <= 1) return s;
 5         int left=0,right =0,maxLength =0,startIdx =0;
 6         for(int i=0;i<s.length();++i)
 7         {
 8             if(s[i]==s[i+1])    //toot
 9             {
10                 left = i;
11                 right = i+1;
12                 searchPalindrome(s,left,right,startIdx, maxLength);
13                 if(s[i+1]==s[i+2])　　//ccc
14                 {
15                     left = i;
16                     right = i+2;
17                     searchPalindrome(s,left,right,startIdx, maxLength);
18                 }
19             }
20             else
21             {
22                 left = right = i;
23                 searchPalindrome(s,left,right,startIdx, maxLength);　　//ana
24                 
25             }
26         }
27         return s.substr(startIdx,maxLength);
28     }
29     void searchPalindrome(string &s, int left, int right, int &startIdx, int &len)
30     {
31         int step =1;
32         while((left-step) >=0 && (right+step) <s.length())
33         {
34             if(s[left-step] != s[right+step])
35             {
36                 break;
37             }
38             else
39             {
40                 step =step +1;
41             }
42         }
43         int width = right-left + 2*step -1;
44         if(width > len)
45         {
46             startIdx = left-step+1;
47             len = width;
48         }
49         
50     }
51 };