【LeetCode 热题 100】5. 最长回文子串——中心扩散法
Problem: 5. 最长回文子串
文章目录
- 整体思路
- 完整代码
- 时空复杂度
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
整体思路
这段代码旨在解决经典的 “最长回文子串” (Longest Palindromic Substring) 问题。问题要求在一个给定的字符串 S 中，找到一个最长的、内容左右对称的连续子串。
该算法采用了一种非常高效且简洁的 中心扩展 (Expand From Center) 算法。其核心思想是，任何一个回文串，都有一个中心。这个中心可能是一个字符（对于奇数长度的回文串，如 “aba” 的中心是 ‘b’），也可能是两个字符之间的空隙（对于偶数长度的回文串，如 “abba” 的中心在两个 ‘b’ 之间）。
算法的逻辑步骤如下：
-
统一中心处理：
- 该算法最巧妙的一点是，它通过一个
for循环for (int i = 0; i < 2 * n - 1; i++)来遍历所有可能的中心。 - 一个长度为
n的字符串，有n个单字符中心和n-1个字符间的中心，总共2n-1个。 - 通过
l = i / 2和r = (i + 1) / 2这两个计算，可以巧妙地将这2n-1个虚拟中心索引i映射到字符串的实际索引起点：- 当
i是偶数时（例如i=4），l和r会相等（l=2, r=2），这对应一个单字符中心，用于查找奇数长度的回文串。 - 当
i是奇数时（例如i=5），r会比l大1（l=2, r=3），这对应一个字符间中心，用于查找偶数长度的回文串。
- 当
- 该算法最巧妙的一点是，它通过一个
-
从中心向两边扩展：
- 对于每一个确定的中心
(l, r)，算法进入一个while循环。 - 这个循环同时将左指针
l向左移动 (l--) 和右指针r向右移动 (r++)，并持续检查以下条件：
a. 指针没有越界 (l >= 0 && r < n)。
b. 两边指针指向的字符相等 (s[l] == s[r])。 - 只要这些条件满足，就说明当前
[l, r]范围内的子串是一个回文串，可以继续尝试扩展。
- 对于每一个确定的中心
-
更新最长回文串记录：
- 当
while循环因不满足条件而终止时，最后一个有效的回文串是在l和r停止移动之前的位置，即[l+1, r-1]。 - 该回文串的长度为
(r-1) - (l+1) + 1 = r - l - 1。 - 算法将这个长度与已记录的最长回文串的长度进行比较。如果当前找到的更长，就更新
ansLeft和ansRight来记录这个新发现的最长回文串的边界。
- 当
-
返回结果：
- 在遍历完所有
2n-1个中心后，ansLeft和ansRight中存储的就是全局最长回文子串的起始索引（包含）和结束索引（不包含）。 - 最后，使用
S.substring(ansLeft, ansRight)截取并返回结果。
- 在遍历完所有
完整代码
class Solution {/*** 找到字符串 S 中的最长回文子串。* @param S 输入的字符串* @return 最长的回文子串*/public String longestPalindrome(String S) {// 将字符串转换为字符数组，可以略微提高字符访问效率。char[] s = S.toCharArray();int n = s.length;// ansLeft: 记录最长回文子串的起始索引（包含）。int ansLeft = 0;// ansRight: 记录最长回文子串的结束索引（不包含）。int ansRight = 0;// 核心循环：遍历所有 2n-1 个可能的中心。// i 是一个虚拟的中心索引。for (int i = 0; i < 2 * n - 1; i++) {// 通过 i 计算出中心扩展的起始左右指针。// 如果 i 是偶数, l=r, 对应单字符中心 (奇数长度回文串)。// 如果 i 是奇数, r=l+1, 对应字符间中心 (偶数长度回文串)。int l = i / 2;int r = (i + 1) / 2;// 从中心 (l, r) 向两边扩展，寻找回文串。while (l >= 0 && r < n && s[l] == s[r]) {l--;r++;}// 循环结束后，最后一个有效回文串的边界是 [l+1, r-1]。// 其长度为 (r-1) - (l+1) + 1 = r - l - 1。// 当前记录的最长长度为 ansRight - ansLeft。if (r - l - 1 > ansRight - ansLeft) {// 如果找到了更长的回文串，则更新记录。// 新的起始索引是 l+1。ansLeft = l + 1;// 新的结束索引（不包含）是 r。ansRight = r;}}// 根据记录的边界，从原始字符串 S 中截取最长回文子串。return S.substring(ansLeft, ansRight);}
}
时空复杂度
时间复杂度：O(N^2)
- 外层循环：
for (int i = 0; i < 2 * n - 1; i++)遍历了2n-1次，其复杂度为 O(N)。 - 内层循环：
while (...)循环是从每个中心向外扩展。在最坏的情况下（例如，字符串本身就是一个大回文串 “aaaaa…”），从中心开始的扩展可能会一直延伸到字符串的两端。每次扩展的操作数最多是N/2次（向左N/2，向右N/2）。因此，内层循环的复杂度是 O(N)。 - 综合分析：
总的时间复杂度是外层循环和内层循环复杂度的乘积。即O(N) * O(N)= O(N^2)。
空间复杂度：O(1)
- 主要存储开销：算法的核心逻辑只使用了固定数量的整型变量（
n,ansLeft,ansRight,i,l,r）来存储指针和结果边界。 toCharArray()：char[] s = S.toCharArray();创建了字符串的一个副本，占用了 O(N) 的空间。然而，在标准的算法复杂度分析中，这种对输入的表示转换通常不被计入额外辅助空间（auxiliary space），因为核心算法本身（指针操作）并不需要这部分空间（可以直接使用S.charAt()）。- 综合分析：
如果我们只考虑算法逻辑本身所需的额外空间，那么空间复杂度为 O(1)。