企业官网建设流程全解析

这道题是回文串问题的经典代表，核心思路有三种：中心扩展、动态规划、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[i+1] 之间为中心
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 已经越界或不匹配
// 回文串范围是 [left+1, right-1]，长度为 right - left - 1
return right - left - 1;
}
}

复杂度：
- 时间：O(n²)
- 空间：O(1)

解法二：动态规划

核心思想：如果一个子串 s[i...j] 是回文串，那么它满足：
- s[i] == s[j]（两端字符相同）
- s[i+1...j-1] 也是回文串（内部子串也是回文）

状态转移方程：

dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]

边界条件：
- 单个字符一定是回文：dp[i][i] = true
- 两个相同相邻字符是回文：dp[i][i+1] = (s[i] == s[i+1])

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 算法会是加分项。

回文子串还有个经典变体——最长回文子序列（不要求连续），思路完全不同，要不要顺带看看？