这道题是回文串问题的经典代表核心思路有三种中心扩展、动态规划、Manacher 算法。面试中最常考的是前两种下面逐一讲解。解法一中心扩展法推荐核心思想回文串是对称的所以可以从每个字符或两个字符之间的空隙向两边扩展找到以该位置为中心的最长回文串。注意回文中心有两种情况- 奇数长度以单个字符为中心如 aba中心是 b- 偶数长度以两个字符之间为中心如 abba中心是两个 b 之间class Solution {public String longestPalindrome(String s) {if (s null || s.length() 2) return s;int start 0, maxLen 0;for (int i 0; i s.length(); i) {// 奇数长度以 s[i] 为中心int len1 expandFromCenter(s, i, i);// 偶数长度以 s[i] 和 s[i1] 之间为中心int len2 expandFromCenter(s, i, i 1);int len Math.max(len1, len2);if (len maxLen) {maxLen len;start i - (len - 1) / 2; // 计算回文串的起始位置}}return s.substring(start, start maxLen);}// 从中心向两边扩展返回回文串的长度private int expandFromCenter(String s, int left, int right) {while (left 0 right s.length() s.charAt(left) s.charAt(right)) {left--;right;}// 退出循环时left 和 right 已经越界或不匹配// 回文串范围是 [left1, right-1]长度为 right - left - 1return right - left - 1;}}复杂度- 时间O(n²)- 空间O(1)解法二动态规划核心思想如果一个子串 s[i...j] 是回文串那么它满足- s[i] s[j]两端字符相同- s[i1...j-1] 也是回文串内部子串也是回文状态转移方程dp[i][j] (s[i] s[j]) dp[i1][j-1]边界条件- 单个字符一定是回文dp[i][i] true- 两个相同相邻字符是回文dp[i][i1] (s[i] s[i1])class Solution {public String longestPalindrome(String s) {int n s.length();if (n 2) return s;boolean[][] dp new boolean[n][n];int start 0, maxLen 1;// 单个字符一定是回文for (int i 0; i n; i) {dp[i][i] true;}// 按子串长度从小到大遍历for (int len 2; len n; len) {for (int i 0; i n - len; i) {int j i len - 1; // 子串右端点if (s.charAt(i) ! s.charAt(j)) {dp[i][j] false;} else {// 两端相同如果长度 3 则一定是回文// 否则看内部子串是否为回文if (len 3) {dp[i][j] true;} else {dp[i][j] dp[i 1][j - 1];}}// 更新最长回文串if (dp[i][j] len maxLen) {maxLen len;start i;}}}return s.substring(start, start maxLen);}}复杂度- 时间O(n²)- 空间O(n²)解法三Manacher 算法进阶Manacher 算法可以在 O(n) 时间内解决最长回文子串问题核心技巧是1. 在字符间插入特殊字符如 #统一奇偶长度2. 利用已计算的回文半径借助对称性避免重复计算class Solution {public String longestPalindrome(String s) {// 预处理插入 #统一奇偶长度// 例如 abc - #a#b#c#StringBuilder sb new StringBuilder(#);for (int i 0; i s.length(); i) {sb.append(s.charAt(i)).append(#);}String t sb.toString();int n t.length();int[] p new int[n]; // p[i] 表示以 t[i] 为中心的回文半径int center 0, right 0; // 当前最右回文串的中心和右边界for (int i 0; i n; i) {// 利用对称性初始化 p[i]int mirror 2 * center - i; // i 关于 center 的对称点if (i right) {p[i] Math.min(right - i, p[mirror]);}// 尝试扩展int left i - (1 p[i]);int r i (1 p[i]);while (left 0 r n t.charAt(left) t.charAt(r)) {p[i];left--;r;}// 更新最右回文边界if (i p[i] right) {center i;right i p[i];}}// 找到最大回文半径对应的中心int maxLen 0, centerIdx 0;for (int i 0; i n; i) {if (p[i] maxLen) {maxLen p[i];centerIdx i;}}// 从预处理字符串的索引还原到原字符串int start (centerIdx - maxLen) / 2;return s.substring(start, start maxLen);}}复杂度- 时间O(n)- 空间O(n)三种解法对比解法 时间复杂度 空间复杂度 适用场景中心扩展 O(n²) O(1) 面试首选代码简洁动态规划 O(n²) O(n²) 适合需要判断所有子串是否回文Manacher O(n) O(n) 追求极致性能竞赛场景面试中推荐写中心扩展法逻辑清晰且空间最优。如果面试官追问能否优化时间复杂度再引出 Manacher 算法会是加分项。回文子串还有个经典变体——最长回文子序列不要求连续思路完全不同要不要顺带看看