LeetCode--Longest Palindromic Substring

有一个比较容易出错的点：反转求最长公共子序列，这是错误的想法

 1 class Solution {
 2 public:
 3     string longestPalindrome(string s) {
 4         int n = s.length();
 5         int longestS = 0;
 6         int maxlen = 1;
 7         bool table[1000][1000] = {false};
 8         int i,j,len;
 9         for(i = 0 ; i < n ; ++i)
10         {
11             table[i][i] = true;
12         }
13         
14         for(i = 0 ; i < n-1; ++i)
15         {
16             if(s[i] == s[i+1])
17             {
18                 table[i][i+1] = true;
19                 longestS = i;
20                 maxlen = 2;
21             }
22         }
23         for(len = 3 ; len <= n ; ++len)
24         {
25             for(i = 0 ; i < n-len+1 ; ++i)
26             {
27                 j = i+len-1;
28                 if(s[i]==s[j] && table[i+1][j-1])
29                 {
30                     table[i][j] = true;
31                     longestS = i;
32                     maxlen = len;
33                 }
34             }
35         }
36         return s.substr(longestS,maxlen);
37     }
38 };

可以优化的，优化为O（1）的空间。就是考虑2*n-1个位置为中间点，然后开始求。