中心扩展法 - 解决回文子串的经典算法

核心思想

中心扩展法的基本思想是：将每个位置（或每对位置）当作回文的中心，然后向两边扩展，检查是否能形成更长的回文

1. 奇数长度回文中心

字符串:  a   b   a
索引:    0   1   2
中心:        ↑
         单个字符中心

• 中心点：单个字符
• 扩展：从 (i, i) 开始向两边扩展

2. 偶数长度回文中心

字符串:  a   b   b   a
索引:    0   1   2   3
中心:        ↑   ↑
         两个字符之间的中心

• 中心点：两个相同字符之间
• 扩展：从 (i, i+1) 开始向两边扩展

步骤1：定义扩展函数

参数接收左起始索引和右起始索引

对于奇数中心：left = i, right = i （从同一个字符开始向两边扩）

对于偶数中心：left = i, right = i + 1 (从相邻的两个字符开始向两边扩)

right - left - 1 位当前回文子串的长度

function expandAroundCenter(left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
        left--;
        right++;
    }
    // 返回回文长度
    return right - left - 1;
}

关键理解：循环结束时，left 和 right 指向的是第一个不满足回文条件的位置。

步骤2：遍历所有可能的中心

start 和 end为回文原字符串中的起始和结束索引

在已知中心索引和回文长度的情况下，更新起始和结束索引，

关于为什么start是Math.floor((maxLen - 1) / 2) ，end是Math.floor(maxLen / 2)？🧐

起始索引：

对于奇数长度回文，中心点i本身算一个字符，剩下的长度(maxlen - 1) / 2 平均分配到左右两侧

对于偶数长度回文，是(maxlen / 2) - 1，就相当于Math.floor((maxlen - 1) / 2)

结束索引：

奇数：maxLen / 2 是小数，Math.floor 得到 (maxLen - 1) / 2

偶数：maxLen / 2 是整数，Math.floor 不影响

for (let i = 0; i < s.length; i++) {
    // 检查两种中心类型
    let len1 = expandAroundCenter(i, i);     // 奇数长度回文
    let len2 = expandAroundCenter(i, i + 1); // 偶数长度回文
    
    let maxLen = Math.max(len1, len2);
    
    // 更新最长回文边界
    if (maxLen > end - start) {
        start = i - Math.floor((maxLen - 1) / 2);
        end = i + Math.floor(maxLen / 2);
    }
}