1. 引言
本文将介绍在Java中如何判断给定字符串是否为回文。回文是指正读反读都相同的字符序列，例如"madam"或"racecar"。作为有经验的开发者，这类基础算法问题应该快速掌握，但实现方式有多种，每种都有其适用场景。
2. 解决方案
下面我们通过几种不同方式实现回文检测，每种方案都有其优缺点，可根据实际需求选择。
2.1. 简单粗暴的双指针法
最直观的方法是同时从字符串两端向中间遍历，逐个字符比较：
public boolean isPalindrome(String text) {
String clean = text.replaceAll("\\s+", "").toLowerCase();
int length = clean.length();
int forward = 0;
int backward = length - 1;
while (backward > forward) {
char forwardChar = clean.charAt(forward++);
char backwardChar = clean.charAt(backward--);
if (forwardChar != backwardChar)
return false;
}
return true;
}
✅ 优点：
- 时间复杂度O(n/2)，空间复杂度O(1)
- 无需额外内存，适合处理超大字符串
⚠️ 注意：需先去除空格并统一大小写，避免"Race Car"这类字符串误判
2.2. 字符串反转法
通过反转字符串后与原字符串比较，实现方式可分为两类：
手动反转实现
public boolean isPalindromeReverseTheString(String text) {
StringBuilder reverse = new StringBuilder();
String clean = text.replaceAll("\\s+", "").toLowerCase();
char[] plain = clean.toCharArray();
for (int i = plain.length - 1; i >= 0; i--) {
reverse.append(plain[i]);
}
return (reverse.toString()).equals(clean);
}
使用StringBuilder/StringBuffer
public boolean isPalindromeUsingStringBuilder(String text) {
String clean = text.replaceAll("\\s+", "").toLowerCase();
StringBuilder plain = new StringBuilder(clean);
StringBuilder reverse = plain.reverse();
return (reverse.toString()).equals(clean);
}
public boolean isPalindromeUsingStringBuffer(String text) {
String clean = text.replaceAll("\\s+", "").toLowerCase();
StringBuffer plain = new StringBuffer(clean);
StringBuffer reverse = plain.reverse();
return (reverse.toString()).equals(clean);
}
❌ 缺点：
- 需要O(n)额外空间存储反转字符串
- StringBuilder和StringBuffer的reverse()方法内部实现效率不如双指针法
2.3. Stream API实现
利用Java 8的流式处理，代码更简洁：
public boolean isPalindromeUsingIntStream(String text) {
String temp = text.replaceAll("\\s+", "").toLowerCase();
return IntStream.range(0, temp.length() / 2)
.noneMatch(i -> temp.charAt(i) != temp.charAt(temp.length() - i - 1));
}
✅ 优点：
- 函数式风格，代码简洁
- 并行流可提升处理速度（对超长字符串有效）
⚠️ 注意：对短字符串而言，流式处理的开销可能超过其优势
2.4. 递归实现
递归是解决此类问题的经典方法，但需注意栈溢出风险：
public boolean isPalindromeRecursive(String text){
String clean = text.replaceAll("\\s+", "").toLowerCase();
return recursivePalindrome(clean,0,clean.length()-1);
}
private boolean recursivePalindrome(String text, int forward, int backward) {
if (forward == backward) {
return true;
}
if ((text.charAt(forward)) != (text.charAt(backward))) {
return false;
}
if (forward < backward + 1) {
return recursivePalindrome(text, forward + 1, backward - 1);
}
return true;
}
❌ 缺点：
- 空间复杂度O(n)（调用栈深度）
- 极长字符串可能导致StackOverflowError
3. 总结
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 双指针法 | O(n) | O(1) | 超大字符串，内存敏感场景 |
| 字符串反转法 | O(n) | O(n) | 简单场景，代码可读性优先 |
| Stream API | O(n) | O(1) | 并行处理，函数式编程风格 |
| 递归法 | O(n) | O(n) | 教学示例，短字符串处理 |
推荐选择：
- 生产环境优先使用双指针法（性能最优）
- 需要代码简洁时考虑Stream API
- 避免在长字符串处理中使用递归
本文所有代码示例可在GitHub仓库获取完整实现。