LeetCode 5: 最长回文字符串

[guodongxiaren]

https://leetcode-cn.com/problems/longest-palindromic-substring 最长回文字符串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例 2：

输入: "cbbd" 输出: "bb"

[guodongxiaren]

官方题解：

https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode/

解法很多。

O(n^2)时间复杂度的中心扩展法简单明了。

O(n)时间复杂度的Manacher（马拉车）算法，在面试时间内准确无误写出太过挑战。

[guodongxiaren]

中心扩展法

class Solution {
public:
    string longestPalindrome(string s) {
        auto expandAroundCenter = [&](string& s, int left, int right) {
            while (left >=0 && right < s.length() && s[left] == s[right]) {
                left--;
                right++;
            }
            // (right-1) - (left+1) + 1 => right - left - 1
            return right - left - 1; 
        };

        int start = 0, max_len = 0;
        for (int i = 0; i < s.length(); ++i) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i+1);
            int len = max(len1, len2);
            if (len > max_len) {
                start = i - (len - 1)/2;
                max_len = len;
            }
        }
        return s.substr(start, max_len);
    }
};