最长回文子串：字符串中的对称之美
大家好！今天我们来探讨一道经典的字符串算法问题——最长回文子串。这个问题不仅在面试中常见，也是理解字符串处理和多种算法技巧的绝佳窗口。让我们一起探索回文字符串的奇妙世界！
🌟 什么是回文？从生活到算法
在深入算法之前，让我们先理解什么是回文。回文是指正着读和倒着读都一样的序列。比如：
- "上海自来水来自海上"
- "madam"
- "racecar"
- "12321"
回文结构在自然界和人类艺术中广泛存在，展现了一种完美的对称之美。在算法世界中，寻找最长回文子串则是对这种对称性的一种探索。
🎯 问题描述：寻找对称的最长片段
给你一个字符串 s，找到 s 中最长的回文子串。
例如：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
输入：s = "cbbd"
输出："bb"🤔 从小例子开始思考
让我们通过分析几个简单例子来理解这个问题：
例子1: "aba"
- 回文子串有: "a", "b", "a", "aba"
- 最长的是 "aba"，长度为3
例子2: "abbc"
- 回文子串有: "a", "b", "b", "c", "bb"
- 最长的是 "bb"，长度为2
通过这些例子，我们发现回文有两种结构：
- 奇数长度，形如 "aba"，有一个中心字符
- 偶数长度，形如 "abba"，有两个中心字符
💡 解决方案：多种思路的碰撞
方法一：中心扩展法
中心扩展法的核心思想是：对于字符串中的每个位置，我们将其视为回文的中心，然后向两边扩展，直到不再形成回文。
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i); // 奇数长度
int len2 = expandAroundCenter(s, i, i + 1); // 偶数长度
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1; // 回文的长度
}
}时间复杂度：O(n²)，每个中心最多扩展n次 空间复杂度：O(1)，只使用了常数额外空间
方法二：动态规划
动态规划的思路是：如果一个字符串是回文，那么去掉首尾字符后仍是回文。我们可以用一个二维数组dp[i][j]表示子串s[i...j]是否为回文。
状态转移方程：
- dp[i][j] = true，如果s[i] == s[j] 且 (j-i <= 2 或 dp[i+1][j-1] == true)
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
String result = "";
// 单个字符都是回文
for (int i = 0; i < n; i++) {
dp[i][i] = true;
result = s.substring(i, i+1);
}
// 检查长度为2的子串
for (int i = 0; i < n-1; i++) {
if (s.charAt(i) == s.charAt(i+1)) {
dp[i][i+1] = true;
result = s.substring(i, i+2);
}
}
// 检查长度大于2的子串
for (int len = 3; 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+1][j-1]) {
dp[i][j] = true;
if (len > result.length()) {
result = s.substring(i, j+1);
}
}
}
}
return result;
}
}时间复杂度：O(n²) 空间复杂度：O(n²)，需要n²大小的dp数组
方法三：Manacher算法
Manacher算法是一种线性时间复杂度的解法，它通过巧妙地利用回文的对称性，避免了不必要的重复计算。
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
// 预处理，插入特殊字符#
StringBuilder sb = new StringBuilder();
sb.append('#');
for (char c : s.toCharArray()) {
sb.append(c).append('#');
}
String t = sb.toString();
int n = t.length();
int[] p = new int[n]; // p[i]表示以i为中心的回文半径
int center = 0, right = 0;
int maxLen = 0, maxCenter = 0;
for (int i = 0; i < n; i++) {
// 利用对称性初始化p[i]
if (right > i) {
p[i] = Math.min(p[2 * center - i], right - i);
}
// 中心扩展
while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n &&
t.charAt(i - p[i] - 1) == t.charAt(i + p[i] + 1)) {
p[i]++;
}
// 更新center和right
if (i + p[i] > right) {
center = i;
right = i + p[i];
}
// 更新最长回文
if (p[i] > maxLen) {
maxLen = p[i];
maxCenter = i;
}
}
// 从处理后的字符串中提取回文
int start = (maxCenter - maxLen) / 2;
return s.substring(start, start + maxLen);
}
}时间复杂度：O(n)，每个位置最多被访问两次 空间复杂度：O(n)，需要存储处理后的字符串和p数组
🎨 图解算法：直观理解过程
中心扩展法图解
以字符串"babab"为例：
b a b a b
0 1 2 3 4
1. 以index=0为中心扩展：
只有"b"，长度1
2. 以index=1为中心扩展：
"a"，长度1
3. 以index=2为中心扩展：
"b" -> "bab" -> "babab"，长度5
4. 以index=3和index=4之间扩展(偶数中心)：
无法形成回文
最长回文子串："babab"，长度5动态规划填表图解
以"babad"为例：
| b | a | b | a | d
--+---+---+---+---+---
b | T | F | T | F | F
a | | T | F | T | F
b | | | T | F | F
a | | | | T | F
d | | | | | T填表过程：
- 对角线全部为T（单个字符都是回文）
- 检查相邻两个字符：dp[0][1] = F, dp[1][2] = F, dp[2][3] = F...
- 检查长度为3的子串：如"bab"，因为首尾相同且中间是回文，所以dp[0][2] = T
- 依此类推...
最长回文子串："bab"，长度3
📊 算法比较：选择最适合的武器
| 中心扩展法 | 动态规划 | Manacher算法 | |
|---|---|---|---|
| 时间复杂度 | O(n²) | O(n²) | O(n) |
| 空间复杂度 | O(1) | O(n²) | O(n) |
| 实现难度 | 简单 | 中等 | 较复杂 |
| 适用场景 | 一般情况 | 需要记录所有回文 | 追求极致性能 |
💫 优化与变体：应对不同挑战
优化一：减少重复计算
在中心扩展法中，我们可以记录已经计算过的结果，避免重复扩展。
优化二：预处理特殊情况
对于全部相同字符的字符串如"aaaaa"，我们可以直接返回整个字符串。
变体一：计算回文子串的数量
除了最长回文子串，有时我们需要计算所有的回文子串数量，这时动态规划方法更为适合。
变体二：允许删除一个字符
如果允许删除一个字符使得结果是回文，问题会变得更加复杂，需要修改我们的算法。
🌈 应用场景：回文算法的广泛应用
回文问题在实际中有许多应用：
- 文本分析和自然语言处理
- DNA序列分析中的回文结构
- 回文密码和加密算法
- 数据存储和检索中的哈希算法
🎓 面试指南：应对回文相关问题
面试中遇到回文问题时：
- 先确认问题类型（最长回文、回文判断、回文数量等）
- 考虑时间和空间限制，选择合适的算法
- 注意边界情况（空字符串、单字符、全相同字符等）
- 清晰表达算法思路，从简单方法开始，逐步优化
🔍 延伸阅读：回文算法的更多探索
- 回文链表的判断
- 回文对（Palindrome Pairs）
- 最长回文子序列（可以不连续）
- 构造回文的最小插入次数
🤔 思考题
如果允许重新排列字符串中的字符，如何找到可以形成的最长回文？
作者：忍者算法
公众号：忍者算法
回文问题展示了算法之美，从简单的中心扩展到复杂的Manacher算法，我们看到了如何通过不同视角解决同一问题。希望这篇文章能帮助你掌握回文算法的精髓，在面试和实际应用中得心应手！
#算法面试 #LeetCode #字符串 #回文 #动态规划
补充：Manacher算法的思维突破
Manacher算法是解决回文问题的"终极武器"，它的核心在于利用已计算回文的信息来加速新回文的判定。想象我们已经找到了一个以center为中心、半径为right的回文，对于在这个范围内的新位置i，可以利用i关于center的对称点j的已知回文信息！
这种对称性利用使得算法能在线性时间内找到最长回文子串，是算法设计中"利用已知信息减少重复计算"的典范。
对于面试中不要求极致性能的场景，中心扩展法通常是最佳选择，因为它简单直观且空间效率高，能很好地平衡复杂度与实现难度。
回文问题的美妙之处在于，它将对称性这个数学概念与字符串处理完美结合，而掌握它的各种解法，将帮助我们构建更丰富的算法思维工具箱！