最长回文子串：中心扩散法与动态规划详解

1. 最长回文子串问题解析

回文串是算法面试中的经典问题，也是检验编程基本功的试金石。所谓回文串，就是正读反读都相同的字符串，比如"aba"、"abba"都是典型的回文串。在实际工程中，回文串检测常用于文本处理、DNA序列分析等领域。

这道题目要求我们从一个给定字符串中找出最长的回文子串。看似简单，但要在O(n²)时间复杂度内解决并不容易。作为力扣第5题，它被标记为中等难度，主要是因为需要同时考虑算法效率和边界条件处理。

2. 中心扩散法详解

2.1 算法原理

中心扩散法的核心思想是：把字符串中的每一个字符（或每两个相邻字符）当作回文串的中心，然后向两边扩散，寻找可能的最长回文子串。

这种方法的优势在于：

• 直观易懂，符合人类判断回文的思维方式
• 时间复杂度为O(n²)，空间复杂度仅为O(1)
• 不需要预处理字符串

2.2 代码实现解析

让我们仔细分析提供的C++实现代码：

cpp复制class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.size();
        int start = 0; // 记录最长回文子串的起始位置
        int end = 0;   // 记录最长回文子串的结束位置
        
        for(int i = 0; i < len; i++) {
            // 处理奇数长度回文
            int left = i, right = i;
            while(left >= 0 && right < len && s[left] == s[right]) {
                left--;
                right++;
            }
            if((right - 1) - (left + 1) > end - start) {
                start = left + 1;
                end = right - 1;
            }