算法刷题系列（十八）：回文串——利用对称性减少比较
算法刷题系列（十八）：回文串——利用对称性减少比较
前一篇通过左右边界维护连续窗口。本篇仍会从两端比较，但关注的是字符串的对称性：若一个区间是回文串，那么它从中心向外的字符必须成对相等。
判断给定区间是否为回文，只需双指针从两端向内，时间复杂度为 O(n)。若要找最长回文子串，逐个枚举所有区间会更慢；枚举回文中心并向两侧扩展，可以在 O(n²) 时间内解决。
一、回文的两种中心
回文串正读和反读相同。中心可能是：
- 一个字符：
racecar的中心是e； - 两个字符之间：
abba的中心在两个b之间。
长度为 n 的字符串共有 n 个单字符中心和 n - 1 个双字符中心，总计 2n - 1 个候选中心。
二、中心扩展
从中心 (left, right) 开始，只要左右字符相同，就继续扩展：
1
2
left -= 1
right += 1
扩展结束后，最后一次移动可能已经越界，因此有效回文区间是：
1
[left + 1, right)
使用半开右端点后，子串长度为 right - left - 1。
三、手动推演
字符串 cabbad 的最长回文是 abba：
1
2
3
4
中心：两个 b 之间
向外：b == b
继续：a == a
继续：c != d，停止
最后一个有效区间对应索引 [1, 5)，长度为 4。
四、Java 实现
下面实现按 Java char（UTF-16 代码单元）比较，示例使用 ASCII 字符。若业务要求以 Unicode 码点或用户感知字符（字素簇）为单位处理，需要先将字符串转换为对应的字符序列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Palindromes {
public static String longestPalindrome(String text) {
if (text == null) {
throw new IllegalArgumentException("text must not be null");
}
if (text.isEmpty()) {
return "";
}
int bestStart = 0;
int bestLength = 1;
for (int center = 0; center < text.length(); center++) {
int[] odd = expand(text, center, center);
int[] even = expand(text, center, center + 1);
if (odd[1] - odd[0] > bestLength) {
bestStart = odd[0];
bestLength = odd[1] - odd[0];
}
if (even[1] - even[0] > bestLength) {
bestStart = even[0];
bestLength = even[1] - even[0];
}
}
return text.substring(bestStart, bestStart + bestLength);
}
private static int[] expand(String text, int left, int right) {
while (left >= 0 && right < text.length()
&& text.charAt(left) == text.charAt(right)) {
left--;
right++;
}
return new int[]{left + 1, right};
}
}
若有多个同样长的答案，此实现返回最先遇到的一个，因为只在长度严格变大时更新答案。
五、Python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def longest_palindrome(text: str) -> str:
if text is None:
raise ValueError("text must not be None")
if not text:
return ""
best_start = 0
best_length = 1
def expand(left: int, right: int) -> tuple[int, int]:
while left >= 0 and right < len(text) and text[left] == text[right]:
left -= 1
right += 1
return left + 1, right
for center in range(len(text)):
for left, right in (
expand(center, center),
expand(center, center + 1),
):
if right - left > best_length:
best_start = left
best_length = right - left
return text[best_start : best_start + best_length]
assert longest_palindrome("cabbad") == "abba"
assert longest_palindrome("racecar") == "racecar"
assert longest_palindrome("abba") == "abba"
assert longest_palindrome("abc") in {"a", "b", "c"}
assert longest_palindrome("") == ""
Python 字符串索引按 Unicode 码点工作；Java 示例按 UTF-16 代码单元工作。ASCII 输入下两者行为一致。处理任意 Unicode 文本时，应明确题目所说“字符”的定义。
六、复杂度与常见错误
每个中心最多向外比较 O(n) 次，共 O(n) 个中心，因此时间复杂度为 O(n²)，额外空间为 O(1)（不计返回子串）。
常见错误包括：
- 只枚举单字符中心：会漏掉偶数长度回文。
- 边界检查放在字符访问之后：应先保证
left >= 0、right < n。 - 扩展结束后直接使用当前指针：要排除最后一次失败比较的位置。
- 只求最长回文却枚举所有子串：候选区间有
O(n²)个，每次重新验证可能导致O(n³)。 - 忽略字符单位：Java UTF-16 索引不总等同于 Unicode 码点或用户看到的字符。
七、与下一篇的连接
回文问题利用对称性减少比较。括号序列则利用前缀中“左括号数量不能落后于右括号”的约束判断合法性；嵌套层次需要栈保存尚未匹配的左括号。下一篇将进一步区分括号匹配与最长有效括号子串。
小结
最长回文子串可以枚举奇数和偶数两类中心，并从中心向两侧扩展。关键边界是扩展后返回 [left + 1, right)，复杂度为 O(n²)。处理 Unicode 文本时，先定义字符和索引的语义。