【OJ题解】最长回文子串

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

个人专栏:

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

题目链接

最长回文子串

解题思路

1. 初步判断

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

2. 回文子串性质

回文子串的性质如下：

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

1. 中心是一个字符（left 和 right 指向相同位置）。
2. 中心是两个字符（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++;
        }
    }
};

代码要点

• 边界判断：注意循环条件中的边界检查，确保 left 和 right 不越界。
• 引用传递：需要更新的数据（如 start 和 maxlen）应通过引用传递。

总结

• 解题思路清晰：基于中心扩展法。
• 时间复杂度可接受： (O(n^2))，适用于中小规模的字符串问题。
• 代码逻辑简洁高效：易于理解与扩展。

如果有任何疑问，欢迎在评论区留言指正，谢谢支持！