首页 > 代码库 > Longest Palindrome Substring
Longest Palindrome Substring
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 middle15 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 };
Longest Palindrome Substring