【OJ题解】最长回文子串

个人主页: 起名字真南的CSDN博客

个人专栏:

【数据结构初阶】 📘 基础数据结构
【C语言】 💻 C语言编程技巧
【C++】 🚀 进阶C++
【OJ题解】 📝 题解精讲

题目链接

最长回文子串

解题思路

1. 初步判断

如果字符串为空，直接返回空字符串。

2. 回文子串性质

回文子串的性质如下：
在这里插入图片描述

因此，判断回文子串时需要考虑两种情况：

中心是一个字符（left 和 right 指向相同位置）。
中心是两个字符（left 指向左边，right 指向右边）。

接下来需要向两边展开，在展开的过程中判断字符是否相同。

3. 判断是否为回文子串

为了实现上述判断，我们需要以下参数：

不需要改变（每次进入循环重新更新的参数）：
- left，right：当前中心点。
- string：原字符串。
需要改变（可保留数据的条件变量）：
- maxlen：记录当前最大回文子串的长度。
- start：回文子串的起始位置（遇到更大的回文子串时更新）。

4. 时间与空间复杂度

空间复杂度：只需开辟少量临时变量，复杂度为 (O(1))。
时间复杂度：需遍历字符串的两种中心，复杂度为 (O(n^2))。

代码实现

以下为代码示例，基于 C++：

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.empty())
            return "";  // 特殊情况处理

        int begin = 0;   // 起始位置
        int maxlen = 0;  // 最大长度

        for(int i = 0; i < s.size(); i++) {
            // 情况1：以单个字符为中心
            Check(s, i, i, begin, maxlen);
            // 情况2：以两个字符为中心
            Check(s, i, i + 1, begin, maxlen);
        }

        // 返回最长回文子串
        return s.substr(begin, maxlen);
    }

    void Check(string& s, int left, int right, int& start, int& maxlen) {
        // 向两边扩展，检查是否为回文
        while(left >= 0 && right < s.size() && s[left] == s[right]) {
            int curlen = right - left + 1;  // 当前回文子串长度
            if(curlen > maxlen) {
                // 更新最大长度与起始位置
                start = left;
                maxlen = curlen;
            }
            left--;
            right++;
        }
    }
};