跳到主要内容

最长回文子串

题目描述​

给你一个字符串 s，找到 s 中最长的回文子串。

示例​

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

提示：

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成

解题思路​

中心扩展法

从字符串的每个字符出发，向两边扩展，判断是否为回文串。

时间复杂度：O(n²) 空间复杂度：O(1)

C++ 解法​

#include <string>

class Solution {
public:
    std::string longestPalindrome(std::string s)
    {
        // 以每个字符为中心，向两边扩展
        int n = s.size();
        if (n == 0) return "";
        std::string res = "";
        for (int i = 0; i < n; i++) {
            std::string s1 = palindrome(s, i, i);     // 奇数长度的回文串
            std::string s2 = palindrome(s, i, i + 1); // 偶数长度的回文串
            res = res.size() >= s1.size() ? res : s1;
            res = res.size() >= s2.size() ? res : s2;
        }
        return res;
    }

    // 返回回文字符串 使用中心扩散法
    std::string palindrome(std::string s, int l, int r)
    {
        int len = s.size();
        while (l >= 0 && r < len && s[l] == s[r]) {
            l--;
            r++;
        }

        // 循环结束时 l和r已经超出回文串的左右边界
        // 所以l+1和r-1是回文串的左右边界
        // 子串的起始位置为l+1,长度为(r-1)-(l+1)+1 = r-l-1
        return s.substr(l + 1, r - l - 1);
    }
};

LeetCode链接： 5. 最长回文子串