首页 > 代码库 > 5. Longest Palindromic Substring(C++)

5. Longest Palindromic Substring(C++)

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"

答案:

class Solution {
public:
  string longestPalindrome(string s) {
    if(s.size()<2){
      return s;
    }
    int len = s.size(), maxlen = 1, maxleft = 0, left, right;
    for(int i=0;i<len&&len-i > maxlen/2;){
      left = right = i;
      while(right<len-1 && s[right]==s[right+1]){
        right++;
      }
      i=right+1;
      while(right<len-1 && left>0 && s[left-1]==s[right+1]){
        right++;
        left--;
      }
      if(maxlen<right-left+1){
        maxleft = left;
        maxlen =right-left+1;
      }
    }
    return s.substr(maxleft,maxlen);
  }
};

5. Longest Palindromic Substring(C++)