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.
Analyse: Consider every index i in the string. Since there are two possibilities of a palindrome: odd size or even size. If i is in the right middle of a palindrome (odd size), expand the substring starting at i towards left and right part (i - 1 && i + 1, i - 2 && i + 2...), update the result; If i and its neighbor are in the right middle of a palindrome(even size), we only consider its right neighbor because the left neighbor of i‘s right neighbor is i! Expand i and i + 1 towards left and right part (i - 1 && i + 1 + 1, i - 2 && i + 1 + 2, i - 3 && i + 1 + 3...), and update result. Be aware of that all index should be [0, s.size() - 1].
1 class Solution { 2 public: 3 string longestPalindrome(string s) { 4 string result; 5 for (int i = 0; i < s.size(); i++) { 6 // i is in the right middle 7 int start = i, end = i; 8 while(start >= 0 && end < s.size() && s[start] == s[end]) { 9 start--; 10 end++; 11 } 12 result = end - start - 1 < result.size() ? result : s.substr(start + 1, end - start - 1); 13 14 // i and i + 1 is in the right middle 15 start = i, end = i + 1; 16 while(start >= 0 && end < s.size() && s[start] == s[end]) { 17 start--; 18 end++; 19 } 20 result = end - start - 1 < result.size() ? result : s.substr(start + 1, end - start - 1); 21 } 22 return result; 23 } 24 };
原文：http://www.cnblogs.com/amazingzoe/p/5887351.html