今天先上一種解法，遞歸：
class Solution {public: string longestPalindrome(string s) { if(s.empty()) return 0; int start_pos = 0, max_len = 1; //start_pos default 0 because max_len default 1 const int len = s.length(); for(int i=0; i<len-1; ++i){ extend_palindrome(s, len, i, i, start_pos, max_len); //assume odd length, try to extend palindrome as possible extend_palindrome(s, len, i, i+1, start_pos, max_len); //assume even length } return s.substr(start_pos, max_len); } void extend_palindrome(string& s, int len, int left, int right, int& start_pos, int& max_len){ while(left >= 0 && right < len && s[left] == s[right]){ --left; ++right; } if(max_len < right-left-1){ start_pos = left + 1; max_len = right - left - 1; } }};為什么要有兩種情況呢：比如abba和abab分別就是和偶數個最長和奇數個最長的情況。
新聞熱點
疑難解答
