最长回文子串怎么解？四种 Go 写法从暴力到 Manacher
给你一个字符串 s，要找出里面最长的那段回文子串。
这就是 LeetCode 第 5 题，面试里出现频率很高。
先说清楚两个容易混的概念。
子串是连续的，子序列可以不连续，这题要的是连续子串。
回文就是正着读反着读一样，比如 aba、abba。
下面按从慢到快的顺序，给四种 Go 解法。
暴力枚举：能过但慢
最直接的思路：枚举所有子串，逐个判断是不是回文，记录最长的那个。
func longestPalindrome(s string) string {
r := []rune(s)
if len(r) < 2 {
return s
}
maxStr := string(r[0])
for i := 0; i < len(r); i++ {
for j := i + 1; j <= len(r); j++ {
if j-i > len(maxStr) && isPalindrome(r[i:j]) {
maxStr = string(r[i:j])
}
}
}
return maxStr
}
func isPalindrome(r []rune) bool {
for l, h := 0, len(r)-1; l < h; l, h = l+1, h-1 {
if r[l] != r[h] {
return false
}
}
return true
}这里有个细节值得提一下。
判断回文不必把整个字符串反转再比较，那样多一次内存分配。
双指针从两头往中间走，一对不相等就直接返回 false，省一半比较。
时间复杂度 O(n³)，枚举子串 O(n²)，每次判断 O(n)。
字符串一长就超时，n 到几千就吃力了。
当练手可以，正式提交不推荐。
中心扩散：一行思路省一个量级
回文有个对称特点：从中心往两边扩展，左右字符相等就继续，不等就停。
所以可以枚举每一个中心，向外扩散找最长回文。
问题是回文长度有奇有偶。
aba 中心是单个字符 b，abba 中心在两个 b 之间。
处理办法是每个位置都试两次。
func longestPalindrome(s string) string {
r := []rune(s)
if len(r) < 2 {
return s
}
start, maxLen := 0, 1
expand := func(l, h int) {
for l >= 0 && h < len(r) && r[l] == r[h] {
l--
h++
}
// 循环结束时 l、h 各多走了一步，真实长度是 h-l-1
if h-l-1 > maxLen {
start = l + 1
maxLen = h - l - 1
}
}
for i := 0; i < len(r); i++ {
expand(i, i) // 奇数长度，中心是单字符
expand(i, i+1) // 偶数长度，中心在两字符之间
}
return string(r[start : start+maxLen])
}时间复杂度 O(n²)，空间 O(1)。
这是面试里最推荐的写法，思路好讲、代码短、不额外占空间。
我自己刷题基本都用这个。
expand 退出后那个 h-l-1 我第一次写的时候算错过，写成了 h-l，结果长度多 2。
调试时打印了几组才反应过来：循环退出前 l 和 h 已经各自越界一格，得把这两格减掉。
动态规划：把判断结果缓存起来
暴力法慢在重复判断。abcba 是回文，那判断 bcb 时其实可以复用结论。
动态规划就是把这种重叠子问题的结果存下来。
定义 dp[i][j] 表示子串 s[i..j] 是不是回文。状态转移：
dp[i][j] = (s[i] == s[j]) && (j - i < 2 || dp[i+1][j-1])意思是：两端字符相等，且去掉两端后的内部也是回文（长度小于 2 时内部为空，直接算回文）。
func longestPalindrome(s string) string {
r := []rune(s)
n := len(r)
if n < 2 {
return s
}
dp := make([][]bool, n)
for i := range dp {
dp[i] = make([]bool, n)
}
start, maxLen := 0, 1
// 注意遍历顺序：i 从大到小，j 从小到大
// 保证算 dp[i][j] 时 dp[i+1][j-1] 已经算好
for i := n - 1; i >= 0; i-- {
for j := i; j < n; j++ {
if r[i] == r[j] && (j-i < 2 || dp[i+1][j-1]) {
dp[i][j] = true
if j-i+1 > maxLen {
start = i
maxLen = j - i + 1
}
}
}
}
return string(r[start : start+maxLen])
}时间复杂度 O(n²)，空间也是 O(n²)。和中心扩散同一量级，但多用了内存。
这里最坑的是遍历顺序。
dp[i][j] 依赖 dp[i+1][j-1]，也就是依赖"更靠下、更靠左"的格子。
所以 i 必须从下往上、j 从左往右。
Manacher：唯一的 O(n) 解法
如果面试官追问能不能做到线性，那就是 Manacher 算法。
它的核心是利用已经算过的回文信息，避免重复扩散。
Manacher 先在每个字符间插入分隔符（比如 #），把奇偶长度统一成奇数处理。
然后维护一个数组记录每个位置的回文半径，借助当前最右回文边界做镜像加速。
func longestPalindrome(s string) string {
if len(s) < 2 {
return s
}
// 预处理：a#b#c，首尾再加哨兵避免越界
t := []rune("^#")
for _, c := range s {
t = append(t, c, '#')
}
t = append(t, '$')
n := len(t)
p := make([]int, n) // p[i] 是以 i 为中心的回文半径
center, right := 0, 0
for i := 1; i < n-1; i++ {
if i < right {
mirror := 2*center - i
p[i] = min(right-i, p[mirror])
}
for t[i+p[i]+1] == t[i-p[i]-1] {
p[i]++
}
if i+p[i] > right {
center, right = i, i+p[i]
}
}
maxLen, centerIdx := 0, 0
for i := 1; i < n-1; i++ {
if p[i] > maxLen {
maxLen = p[i]
centerIdx = i
}
}
start := (centerIdx - maxLen) / 2
return s[start : start+maxLen]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}时间复杂度 O(n)，空间 O(n)。
代码不算长，但理解成本高，镜像那段我也是看了好几遍才彻底搞明白。
说实话，除非面试明确要求线性，否则用中心扩散就够了，没必要为了炫技上 Manacher。
注意这版 Manacher 用了 s[start:start+maxLen] 按字节切片，对纯 ASCII 没问题。如果输入含中文等多字节字符，要换成 rune 索引，否则会切坏。
四种解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 暴力枚举 | O(n³) | O(1) | 练手，理解题意 |
| 中心扩散 | O(n²) | O(1) | 面试首选，最实用 |
| 动态规划 | O(n²) | O(n²) | 考察 DP 思维 |
| Manacher | O(n) | O(n) | 追求最优、数据量大 |
实际工作和面试中，中心扩散性价比最高。动态规划适合用来锻炼状态转移的思路。Manacher 属于加分项，不是必备。
常见问题
最长回文子串和最长回文子序列有什么区别？
子串必须连续，子序列可以跳着取。
比如 bbbab，最长回文子串是 bbb，最长回文子序列是 bbbb。
两者解法完全不同，子序列那题要用区间 DP。
中心扩散为什么要扩散两次？
因为回文长度有奇有偶。
奇数长度（如 aba）中心是单个字符，偶数长度（如 abba）中心落在两个字符中间。
每个位置分别按奇、偶各试一次，才不会漏掉答案。
动态规划的遍历顺序为什么不能从上往下？
dp[i][j] 依赖 dp[i+1][j-1]，即依赖行号更大、列号更小的格子。
只有 i 从大到小、j 从小到大遍历，才能保证算当前格子时所依赖的值已经计算完成。
顺序写反结果必错。
处理中文字符串要注意什么？
Go 的 string 按字节存储，中文一个字占 3 字节。
直接用下标切片会切坏字符。建议先转成 []rune 再处理，前面三种解法都这么做了。
Manacher 那版若要支持中文，也得改成 rune 索引。
小结
四种解法各有侧重，记不住没关系，先把中心扩散吃透，应付绝大多数场景足够了。
动态规划帮你建立"缓存子问题"的直觉，Manacher 当作进阶了解。
如果对某种解法的细节还有疑问，或者发现哪里写得不对，欢迎在评论区交流～
版权声明
未经授权，禁止转载本文章。
如需转载请保留原文链接并注明出处。即视为默认获得授权。
未保留原文链接未注明出处或删除链接将视为侵权，必追究法律责任！
本文原文链接： https://fiveyoboy.com/articles/longest-palindromic-substring-go/
备用原文链接： https://blog.fiveyoboy.com/articles/longest-palindromic-substring-go/