Leetcode#5 Longest Palindromic Substring

最初的想法是用动态规划，令palin[i][j]表示s[i..j]是否是回文串，则有递推公式palin[i][j] = s[i] == s[j] && palin[i+1][j-1]。因为递推式只使用相邻层的值，所以编码的时候可以将二维状态数组压缩成一维的。

代码：

 1 string longestPalindrome(string s) {
 2   if (s.empty())
 3     return "";
 4 
 5   vector<bool> palinp(s.length(), true);
 6   int start = 0;
 7   int len = 1;
 8 
 9   for (int i = s.length() - 2; i >= 0; i--) {
10     palinp[i] = true;
11     for (int j = s.length() - 1; j > i; j--) {
12       palinp[j] = s[i] == s[j] && palinp[j - 1];
13       if (palinp[j] && j - i + 1 > len) {
14         len = j - i + 1;
15         start = i;
16       }
17     }
18   }
19 
20   return s.substr(start, len);
21 }

虽然看上去挺好，但DP的时间复杂度是O(n^2)，跟蛮力算法差不多，果然，对于大数据超时了。

这个时候就到了二分法大显身手的时刻了！

二分法枚举回文串的长度，如果找到了，长度翻倍并继续尝试，如果没找到，长度折半并继续。

需要注意的是，奇数长度的回文串和偶数长度的回文串的存在性是相互独立的，如果长度为n的偶数串不是回文串不存在，并不代表长度为n+1的奇数串不是回文串，反之亦然。例如"ab"不是回文串，而"aba"是回文串。所以，在二分枚举的时候，每次都要把奇数长度和偶数长度都枚举一下（m和m-1）以确保正确。

代码：

 1 bool palindromep(string &s, int i, int j) {
 2   while (i < j && s[i] == s[j]) {
 3     i++;
 4     j--;
 5   }
 6   return i >= j;
 7 }
 8 
 9 string longestPalindrome(string s) {
10   int l = 2;
11   int r = s.length();
12   int start = 0;
13   int len = 1;
14 
15   while (l <= r) {
16     int m = (l + r) / 2;
17     for (int i = 0; i + m <= s.length(); i++)
18       if (palindromep(s, i, i + m - 1)) {
19         start = i;
20         len = m;
21         break;
22       }
23     for (int i = 0; i + (m - 1) <= s.length(); i++)
24       if (palindromep(s, i, i + (m - 1) - 1)) {
25         start = i;
26         len = max(len, m - 1);
27         break;
28       }
29     if (m - len <= 1)
30       l = m + 1;
31     else
32       r = m - 1;
33   }
34 
35   return s.substr(start, len);
36 }