算法 5. 最长回文子串

LeetCode https://leetcode.cn/problems/longest-palindromic-substring/

题目描述

给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

思路

回文字符串中心的两侧互为镜像, 回文有可能是xxxabaxxx(中心为奇数)模式, 也可能是xxxabbaxxx(中心为偶数)
所以需要分两种情况检查, 由中心向两侧扩展检查是否相等即可

class Solution {
    public:
    std::string longestPalindrome(const std::string & s) {
        if (s.empty())
            return "";

        int start = 0;
        int max = 0;
        for (int i = 0; i < s.length(); ++i) {
            int len1 = expand(s, i, i);
            int len2 = expand(s, i, i + 1);
            int len = std::max(len1, len2);
            if (len > max) {
                max = len;
                start = i - (len - 1) / 2;
            }
        }
        return s.substr(start, max);
    }
    int expand(const std::string & s, int left, int righ) {
        while (left >= 0 && righ < s.length() && s[left] == s[righ]) {
            --left;
            ++righ;
        }
        return righ - left - 1;
    }
};