1. 概述
在本篇文章中，我们将学习如何判断一个字符串是否是回文串（Palindrome）。回文串是指正着读和反着读都一样的字符串，例如 "radar"、"madam"、"12321" 等。
2. 什么是回文串？
回文串是指围绕中心对称的字符串。
举个例子：
如上图所示，第一个字符和最后一个字符相同，第二个字符和倒数第二个字符相同，依此类推。
这可以引出一个递归定义：一个字符串 x = x1x2...xn 是回文串，当且仅当 x1 == xn 且 x2...xn-1 也是回文串。递归终止条件是：
- 空字符串是回文串（长度为 0）
- 单个字符也是回文串（长度为 1）
所以，完整的递归定义如下：
2.1 奇数长度与偶数长度的情况
该定义是否适用于奇数和偶数长度的字符串？
- 偶数长度：递归过程最终会在中间两个字符之间结束，这两个字符是最后一组需要比较的字符。
- 奇数长度：递归过程最终会到达中间字符，而长度为 1 的字符串本身就是回文串。
示意图如下：
偶数长度的回文串：
奇数长度的回文串：
3. 递归算法实现
我们可以根据上述定义实现一个递归算法：
public boolean isPalindrome(String s) {
if (s.length() <= 1) {
return true;
}
if (s.charAt(0) != s.charAt(s.length() - 1)) {
return false;
}
return isPalindrome(s.substring(1, s.length() - 1));
}
3.1 时间复杂度分析
最坏情况下（字符串是回文），我们需要检查所有字符对，因此时间复杂度为 **O(n)**。
⚠️ 但要注意，如果字符串非常长，递归调用栈会很深，可能会导致 StackOverflowError。此时建议改用迭代方式实现。
4. 迭代算法实现
为了规避递归带来的栈溢出问题，我们可以将算法改写为迭代版本：
public boolean isPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while (left <= right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
4.1 算法说明
- 初始化两个指针：
left从左向右移动，right从右向左移动 - 每次比较
s[left]和s[right] - 如果不相等，立即返回
false - 如果遍历完整个字符串，说明是回文串，返回
true
✅ 优点：无递归调用，避免栈溢出问题
✅ 时间复杂度同样是 O(n)
5. 总结
| 方法 | 时间复杂度 | 是否可能栈溢出 | 适用场景 |
|---|---|---|---|
| 递归 | O(n) | ✅ 是 | 简单实现、教学用途 |
| 迭代 | O(n) | ❌ 否 | 实际项目推荐使用 |
✅ 建议：实际开发中推荐使用迭代版本，避免因字符串过长导致的栈溢出问题。
⚠️ 踩坑提醒：注意 Java 中 substring 的索引范围是左闭右开 [start, end)，容易出错。
6. 附：完整测试代码
以下是一个完整的测试类，包含多个测试用例：
public class PalindromeCheckerTest {
@Test
public void testEmptyString() {
assertTrue(isPalindrome(""));
}
@Test
public void testSingleCharacter() {
assertTrue(isPalindrome("a"));
}
@Test
public void testEvenLengthPalindrome() {
assertTrue(isPalindrome("abba"));
}
@Test
public void testOddLengthPalindrome() {
assertTrue(isPalindrome("madam"));
}
@Test
public void testNonPalindrome() {
assertFalse(isPalindrome("hello"));
}
@Test
public void testLongPalindrome() {
assertTrue(isPalindrome("1234567890987654321"));
}
@Test
public void testLongNonPalindrome() {
assertFalse(isPalindrome("12345678909876543210"));
}
}