力扣5题 最长回文子串解题思路与C++代码实现解析

一、问题背景与初步思考

力扣第5题要求找到给定字符串中的最长回文子串。回文字符串是指正序和倒序相同的字符串，"aba"或"abba"。解决此问题的关键在于如何高效地寻找所有可能的回文子串并确定其长度。可以考虑暴力解法，即枚举所有子串并逐一判断是否为回文，但这种方法的时间复杂度较高。为了提高效率，我们可以采用中心扩展法或动态规划等更优策略。

在C++实现过程中，我们需要定义一个函数来判断子串是否为回文，并通过遍历字符串逐步构建最优解。为了增强代码的可读性和性能，我们还可以利用指针操作来优化内存访问。

二、中心扩展法详解

中心扩展法是一种常用的解决回文子串问题的方法。该方法的基本思想是：对于每个字符（包括两个字符之间的间隙），假设它是回文的中心，向两边扩展，直到无法构成回文为止。这种方法的时间复杂度为O(n^2)，空间复杂度为O(1)。

在实现时，需要编写一个辅助函数`expandAroundCenter`，用于从指定的中心位置开始向两侧扩展并验证回文性质。接着，在主函数中遍历字符串的所有可能中心点，记录每次扩展得到的最大回文长度及其起始位置。

三、案例分析与代码实现

class Solution { 
public: 
    string longestPalindrome(string s) { 
        if (s.empty()) return ""; 
        int start =0, end = 0; 
        for (int i = 0; i < s.size(); ++i) { 
            int len1 = expandAroundCenter(s, i, i); 
            int len2 = expandAroundCenter(s, i, i + 1); 
            int len = max(len1, len2); 
            if (len > end - start) { 
                start = i - (len - 1) / 2; 
                end = i + len / 2; 
            } 
        }
        return s.substr(start, end - start + 1); 
    } 
private: 
    int expandAroundCenter(const string& s, int left, int right) { 
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            --left; ++right; 
        } 
        return right - left - 1; 
    } 
}; 
int main() {
    Solution sol; 
    string str = "babad"; 
    cout << "Longest Palindromic Substring: " << sol.longestPalindrome(str) << endl; 
    return 0; 
}

四、动态规划法对比

除了中心扩展法，动态规划也是一种有效的解决方案。它通过构建二维表来存储子串的回文信息，从而避免重复计算。由于需要额外的空间来保存中间结果，动态规划的空间复杂度较高，通常为O(n^2)。

动态规划的优势在于易于理解和实现，尤其适合处理大规模数据集。相比之下，中心扩展法则更适合于简单直接的应用场景。