思路： 这道题比较难，有一个解释很好：
Brute force solution, O(N3):The obvious brute force solution is to pick all possible starting and ending positions for a substring, and verify if it is a palindrome. There are a total of C(N, 2) such substrings (excluding the trivial solution where a character itself is a palindrome).
Since verifying each substring takes O(N) time, the run time complexity is O(N3).
Dynamic programming solution, O(N2) time and O(N2) space:To improve over the brute force solution from a DP approach, first think how we can avoid unnecessary re-computation in validating palindromes. Consider the case “ababa”. If we already knew that “bab” is a palindrome, it is obvious that “ababa” must be a palindrome since the two left and right end letters are the same.
Stated more formally below:
Define P[ i, j ] ← true iff the substring S i … S j is a palindrome, otherwise false.Therefore,
P[ i, j ] ← ( P[ i+1, j-1 ] and S i = S j )The base cases are:
P[ i, i ] ← true P[ i, i+1 ] ← ( S i = S i+1 ) 代码： 1 class Solution { 2 public: 3 string longestPalindrome(string s) { 4 // Start typing your C/C++ solution below 5 // DO NOT write int main() function 6 string result; 7 8 int n = s.length(); 9 int longestBegin = 0; 10 int maxLen = 1; 11 vector<vector<bool> > table(1000, vector<bool>(1000, false)); 12 13 for (int i = 0; i < n; i++) 14 table[i][i] = true; 15 16 for (int i = 0; i < n-1; i++){ 17 18 if (s[i] == s[i+1]) { 19 20 table[i][i+1] = true; 21 longestBegin = i; 22 maxLen = 2; 23 } 24 } 25 26 for (int len = 3; len <= n; len++) 27 for (int i = 0; i < n-len+1; i++) { 28 29 int j = i+len-1; 30 if (s[i] == s[j] && table[i+1][j-1]) { 31 table[i][j] = true; 32 longestBegin = i; 33 maxLen = len; 34 } 35 } 36 return s.substr(longestBegin, maxLen); 37 } 38 };
A simpler approach, O(N2) time and O(1) space:In fact, we could solve it in O(N2) time without any extra space.
We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only 2N-1 such centers.
You might be asking why there are 2N-1 but not N centers? The reason is the center of a palindrome can be in between two letters. Such palindromes have even number of letters (such as “abba”) and its center are between the two ‘b’s.
Since expanding a palindrome around its center could take O(N) time, the overall complexity is O(N2).
1 class Solution { 2 public: 3 4 string expandAroundCenter(string s, int c1, int c2) { 5 6 int l = c1, r = c2; 7 int n = s.length(); 8 9 while (l >= 0 && r <= n-1 && s[l] == s[r]) { 10 11 l--; 12 r++; 13 } 14 return s.substr(l+1, r-l-1); 15 } 16 17 18 string longestPalindrome(string s) { 19 20 int n = s.length(); 21 22 if (n == 0) return ""; 23 string longest = s.substr(0, 1); // a single char itself is a palindrome 24 25 for (int i = 0; i < n-1; i++) { 26 27 string p1 = expandAroundCenter(s, i, i); 28 if (p1.length() > longest.length()) 29 longest = p1; 30 string p2 = expandAroundCenter(s, i, i+1); 31 if (p2.length() > longest.length()) 32 longest = p2; 33 } 34 35 return longest; 36 } 37 };
转载于:https://www.cnblogs.com/tanghulu321/archive/2013/05/13/3075137.html
相关资源：数据结构—成绩单生成器