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.
Solution: 1. Time O(n^2), Space O(n^2)
2. Time O(n^2), Space
O(n)
3. Time O(n^2), Space O(1) (actually much more efficient than
1 & 2)
4. Time O(n), Space O(n) (Manacher‘s Algorithm)
1 class Solution { 2 public: 3 string longestPalindrome(string s) { 4 int N = s.size(); 5 bool dp[N][N]; 6 pair<int, int> res = make_pair(0,0); 7 for(int k = 0; k < N; k++) { 8 for(int i = 0; i < N-k; i++) { 9 if(k == 0 || k == 1) { 10 dp[i][i+k] = s[i] == s[i+k]; 11 } 12 else { 13 dp[i][i+k] = s[i] == s[i+k] ? dp[i+1][i+k-1] : false; 14 } 15 if(dp[i][i+k] && k +1 > res.second) { 16 res = make_pair(i,k+1); 17 } 18 } 19 } 20 return s.substr(res.first, res.second); 21 22 } 23 };
Longest Palindromic Substring,布布扣,bubuko.com
原文：http://www.cnblogs.com/zhengjiankang/p/3682054.html