【LeetCode】005. 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.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

题解：

Solution 1

　　暴力搜索，所有可能，注意到"bab"和"baab"两种类型的回文字符串即可。

 1 class Solution {
 2 public:
 3     string longestPalindrome(string s) {
 4         int start = 0, len = 0;
 5         int n = s.size();
 6         if (n < 2)
 7             return s;
 8         for (int i = 0; i < n - 1; ++i) {
 9             rangeOfPalindrome(s, i, i + 1, start, len); // "baab"
10             rangeOfPalindrome(s, i, i, start, len);   // "bab"
11         }
12         return s.substr(start, len);
13     }
14     
15     void rangeOfPalindrome(const string& s, int left, int right, int& start, int& len) {
16         int length = len;
17         int step = 0;
18         while ((left - step >= 0) && (right + step < s.size())) {
19             if (s[left - step] != s[right + step])
20                 break;
21             ++step;
22         }
23         length = 2 * (step - 1) + right - left + 1;
24         if (length > len) {
25             len = length;
26             start = left - (step - 1);
27         }
28     }
29 
30 };

　　代码简化：

 1 class Solution {
 2 public:
 3     string longestPalindrome(string s) {
 4         string res;
 5         int n = s.size(), idx = 0, len = 0;
 6         for (int i = 0; i < n; ++i) {
 7             search(s, i, i, idx, len);
 8             search(s, i, i + 1, idx, len);
 9         }
10         return s.substr(idx, len);
11     }
12     void search(const string& s, int i, int j, int& idx, int& len) {
13         while (i >= 0 && j < s.size() && s[i] == s[j]) {
14             --i;
15             ++j;
16         }
17         if (len < j - i - 1) {
18             len = j - i - 1;
19             idx = i + 1;
20         }
21     }
22 };

Soluion 2

　　DP问题。一个长度为 n（n>1) 的回文字符串S（s1, s2,...,sn)，若将字符s0和sn+1分别放置在S的首尾，此时如果s0 == sn+1,那么新的字符串S'也一定是回文字符串。

　　那么递归式为 dp[i][j] = 1 if i == j

　　　　　　　　　　　= s[i] == s[j]　 if i + 1 = j

= s[i] == s[j] && dp[i + 1][j - 1] if i + 1 < j

 1 class Solution {
 2 public:
 3     string longestPalindrome(string s) {
 4         int n = s.size();
 5         if (n < 1)
 6             return s;
 7         int len = 1, start = 0;
 8         vector<vector<int>> dp(n, vector<int>(n, 0));
 9         
10         for (int i = 0; i < n; ++i) {
11             for (int j = 0; j <= i; ++j) {
12                 dp[j][i] = (s[i] == s[j]) && (i - j <= 1 || dp[j + 1][i - 1]);
13                 if (dp[j][i] && len < i - j + 1) {
14                     len = i - j + 1;
15                     start = j;
16                 }
17             }
18         }
19         
20         return s.substr(start, len);
21     }
22 };

　　Manacher算法

Solution 3