Longest Palindromic Substring(C++ code)

LeetCode Longest Palindromic Substring, Nov 11 '11

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.

思路：回文的递归在于：去掉两头还是回文。基于这个思路，对每个点i, 计算以i为中心(奇数回文)或者以i为中心偏右(偶数回文)能扩展的最长长度，一旦出现不是回文，break就行了。最坏情况下还是要O(n^2),但是比我一开始用数组存结果快，能过大集合了。

0. string longestPalindrome(string s) {  
1.   
2.     string res;  
3.   
4.     if(s.empty()) return res;  
5.   
6.     int start = 0, n = s.length();  
7.   
8.     int longest = 1;  
9.   
10.     for(int i = 1; i < n; i++){  
11.   
12.        //j in center  
13.        for(int j = 1; j <= min(i, n-i-1); j++){  
14.   
15.           if(s[i+j] != s[i-j]){  
16.   
17.              if( longest < 2*j - 1){  
18.   
19.                start = i - j + 1;  longest = 2*j - 1;  
20.              }  
21.              break;  
22.          }  
23.   
24.          if(j == min(i,n-i-1) && s[i+j] == s[i-j]){  
25.   
26.              if(longest < 2*j + 1 ){  
27.   
28.                start = i - j ;  longest = 2*j + 1;  
29.              }  
30.          }  
31.      }  
32.   
33.       //i in right center  
34.       for(int j = 0; j < min(i,n-i); j++ ){  
35.   
36.          if(s[i+j]!= s[i-1-j]){  
37.   
38.              if(longest < 2*j ){  
39.   
40.                start = i - j ;  longest = 2*j ;  
41.              }  
42.   
43.              break;  
44.          }  
45.   
46.          if(j == min(i,n-i) - 1 && s[i+j] == s[i-1-j]){  
47.   
48.              if(longest < 2*(j+1) ){  
49.   
50.                start = i - 1 - j ;  longest = 2*(j+1) ;  
51.              }  
52.          }  
53.       }  
54.   }  
55.   
56.  res = s.substr(start, longest);  
57.   
58.  return res;  

这是一开始写的用数组存结果的，这个方法的缺点是有些不必要的计算，比如abca知道b!=c之后，还是要再设定abca的值为false，而用上面改进方法，知道b!=c后，就不用再考虑abca了。

   string longestPalindrome(string s) {
     string res;
     int start = 0, end = 0, longest = 1;
     if(s.empty()) return res;
     vector<vector<bool> > A(s.length(),vector<bool>(false));

     for(int j = 0; j < s.length(); j++){

          A[j][j] = true;

        for(int i = j - 1; i >= 0; i--){

          if(i == j - 1 && s[i] == s[j])  {

             A[i][j] = true;

             if(longest < (j - i + 1)) {

                start = i; end = j; longest = j - i + 1;

             }

          }

          else if(i == j - 1 && s[i] != s[j]) A[i][j] = false;

          else if(A[i+1][j-1] == true && s[i] == s[j]) {

             A[i][j] = true;

             if(longest < (j - i + 1)) {

                start = i; end = j; longest = j - i + 1;

             }

          }

          else A[i][j] = false;

        }

     }

res = s.substr(start, longest);



return res;

            
 }