中心扩展法（Center Expansion）
📌 定义
中心扩展法是一种用于寻找回文字符串的算法技巧。核心思想是：以每个字符（或字符间隙）为中心，向两边扩展，直到不满足回文条件为止。常用于求解最长回文子串问题。
示例:
字符串: "babad"
中心扩展过程:
中心='b': "b" (长度1)
中心='a': "bab" (长度3) ✓
中心='b': "aba" (长度3) ✓
中心='a': "a" (长度1)
中心='d': "d" (长度1)
最长回文子串: "bab" 或 "aba"
核心思路
回文字符串的特点是以中心对称，因此可以从中心向两边扩展：
- 奇数长度回文：以单个字符为中心（如 “aba”）
- 偶数长度回文：以两个字符之间为中心（如 “abba”）
奇数长度回文 (中心是字符):
a b a
↑ ↑ ↑
← c →
偶数长度回文 (中心是间隙):
a b b a
↑ | | ↑
← c →
复杂度分析
| 指标 | 暴力枚举 | 中心扩展 | Manacher |
|---|---|---|---|
| 时间复杂度 | O(n³) | O(n²) | O(n) |
| 空间复杂度 | O(1) | O(1) | O(n) |
| 实现难度 | 简单 | 中等 | 困难 |
Go 代码
Go 实现
package main
import "fmt"
func longestPalindrome(s string) string {
if len(s) == 0 {
return ""
}
start := 0
maxLen := 0
for i := 0; i < len(s); i++ {
// 奇数长度回文
len1 := expandAroundCenter(s, i, i)
// 偶数长度回文
len2 := expandAroundCenter(s, i, i+1)
currLen := max(len1, len2)
if currLen > maxLen {
maxLen = currLen
start = i - (currLen-1)/2
}
}
return s[start : start+maxLen]
}
func expandAroundCenter(s string, left, right int) int {
for left >= 0 && right < len(s) && s[left] == s[right] {
left--
right++
}
return right - left - 1
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
s := "babad"
result := longestPalindrome(s)
fmt.Printf("'%s' 的最长回文子串: '%s'\n", s, result)
}思路展开
扩展过程示例
字符串: "babad"
索引: 01234
中心 i=0 (b):
奇数: b (长度1)
偶数: 无
中心 i=1 (a):
奇数: bab (扩展到 i-1 和 i+1)
left=0, right=2, s[0]='b', s[2]='b' ✓
left=-1 停止
长度 = 2 - 0 - 1 = 3
偶数: 无 (s[1]≠s[2])
中心 i=2 (b):
奇数: aba (长度3)
偶数: 无
中心 i=3 (a):
奇数: a (长度1)
偶数: ad (s[3]≠s[4])
中心 i=4 (d):
奇数: d (长度1)
偶数: 无
最长回文: "bab" 或 "aba" (长度3)
起始位置计算
当找到长度为len的回文，中心索引为i:
奇数长度回文 (len = 2k + 1):
中心是 s[i]
起始位置 = i - k = i - (len-1)/2
偶数长度回文 (len = 2k):
中心是 s[i] 和 s[i+1] 之间
起始位置 = i - k + 1 = i - (len-2)/2 = i - (len-1)/2 (整除)
统一公式: start = i - (len - 1) / 2
经典题目
LeetCode 问题
扩展问题
- 最短回文串
- 分割回文串
- 验证回文串
⚖️ 优缺点
优点
- ✅ 简单直观：易于理解和实现
- ✅ 空间高效：O(1)额外空间
- ✅ 实用性强：适合大多数场景
- ✅ 无预处理：不需要额外的数据结构
缺点
- ❌ 时间复杂度：O(n²)，不如Manacher的O(n)
- ❌ 重复计算：某些子问题会被重复计算
🎨 应用场景
- 最长回文子串：经典面试题
- 回文检测：快速判断是否为回文
- 文本分析：找出文本中的对称模式
- DNA序列分析：寻找回文序列
💡 中心扩展 vs 其他方法
| 方法 | 时间复杂度 | 空间复杂度 | 实现难度 | 适用场景 |
|---|---|---|---|---|
| 暴力枚举 | O(n³) | O(1) | 简单 | 小规模数据 |
| 中心扩展 | O(n²) | O(1) | 中等 | 通用场景 |
| 动态规划 | O(n²) | O(n²) | 中等 | 需要记录所有回文 |
| Manacher | O(n) | O(n) | 困难 | 大规模数据 |
💡 优化技巧
💡 变体问题
相关主题
- Manacher算法 - 线性时间求最长回文子串
- 滑动窗口 - 双指针技巧
- 最长公共子序列 - 动态规划求解回文
- 字符串算法 - 返回字符串算法总览