[LeetCode]5. Longest Palindromic Substring

原题链接：https://leetcode.com/problems/longest-palindromic-substring/description/

题目意思是给定字符串，要求找到最长的回文字符串。回文字符串就是正着读反着读都一样的字符串，如：“ababa”，“abba”这种

怎么样找到回文字符串呢？我们注意到：回文字符串是两边对称的，不管是奇数还是偶数个字符，它都有中心点。

如：“ababa”中心是第三个（str[2]）字符‘a’；

“abba”中心则为第二个字符（str[1]）和第三个字符（str[2]）之间。

我们只要先选好中心点，然后像两个方向延伸直到不是回文字符串为止即可。

所以对于给定的字符串，我们以它每个字符和字符间空隙为中心点找到最长的回文字符串，最后最长的那个就是输出结果。具体实现代码：

class Solution {
public:
    string expandAroundCenter(string s, int before, int after) {
        if (after == s.length())
            after--;
        
        while (before >= 0 && after <= s.length() - 1 && s[before] == s[after]) {
            before--;
            after++;
        }
        
        return s.substr(before + 1, after - before - 1);
    }
    
    string longestPalindrome(string s) {
        string sub_string, result;
        
        result = "";
        
        for (int i = 0; i < s.length(); i++) {
            sub_string = expandAroundCenter(s, i, i);
            if (sub_string.length() > result.length())
                result = sub_string;
            
            sub_string = expandAroundCenter(s, i, i + 1);
            if (sub_string.length() > result.length())
                result = sub_string;
        }
        
        return result;
    }
};

时间复杂度：O(n​^2​​).

空间复杂度：O(m). m为最长回文字符串的字符个数

总结：回文字符串特点，奇数和偶数个字符中心的处理。