力扣125.验证回文串-双指针
问题描述
在编程面试中，验证回文串是一个经典问题。题目要求我们判断一个字符串是否为回文串，但有两个特殊要求：
只考虑字母和数字字符
忽略字符的大小写
示例 1：
text
输入: "A man, a plan, a canal: Panama" 输出: true 解释: "amanaplanacanalpanama" 是回文串
示例 2：
text
输入: "race a car" 输出: false 解释: "raceacar" 不是回文串
什么是回文串？
回文串是指正着读和反着读都一样的字符串。例如：
"level"
"radar"
"上海自来水来自海上"
解决：双指针法
核心思想
使用两个指针从字符串的两端向中间移动，逐步比较字符是否相同。
算法步骤
初始化指针
左指针
i指向字符串开头右指针
j指向字符串结尾
主循环
当左指针小于右指针时继续比较
跳过非字母数字字符
如果左指针指向的字符不是字母或数字，左指针右移
如果右指针指向的字符不是字母或数字，右指针左移
比较字符
将字符转换为小写后比较
如果相同，两个指针都向中间移动
如果不同，直接返回
false
结束条件
当所有有效字符都比较完毕且都相同时，返回
true
代码实现
class Solution { public boolean isPalindrome(String s) { int i = 0; // 左指针 int j = s.length() - 1; // 右指针 while (i < j) { // 主循环 // 跳过左侧非字母数字字符 if (!Character.isLetterOrDigit(s.charAt(i))) { i++; } // 跳过右侧非字母数字字符 else if (!Character.isLetterOrDigit(s.charAt(j))) { j--; } // 比较字符（忽略大小写） else if (Character.toLowerCase(s.charAt(i)) == Character.toLowerCase(s.charAt(j))) { i++; // 左指针右移 j--; // 右指针左移 } // 字符不同，不是回文串 else { return false; } } return true; // 所有字符匹配 } }算法详解
关键方法解析
1.Character.isLetterOrDigit(char ch)
这个方法用于判断字符是否为字母或数字：
字母：A-Z, a-z
数字：0-9
其他字符（标点、空格等）返回
false
2.Character.toLowerCase(char ch)
将字符转换为小写：
大写字母：A → a
小写字母和数字：保持不变
确保大小写不敏感的比较
复杂度分析
时间复杂度：O(n)
n是字符串的长度每个字符最多被访问一次（左指针或右指针）
最坏情况下需要遍历整个字符串
空间复杂度：O(1)
只使用了常数级别的额外空间
只存储了两个指针和几个临时变量
优化技巧
1. 预处理字符串（备选方案）
可以先清洗字符串，再判断：
public boolean isPalindromeAlternative(String s) { // 1. 转换为小写 // 2. 移除非字母数字字符 String cleaned = s.toLowerCase().replaceAll("[^a-z0-9]", ""); // 3. 判断清洗后的字符串是否为回文 int left = 0, right = cleaned.length() - 1; while (left < right) { if (cleaned.charAt(left) != cleaned.charAt(right)) { return false; } left++; right--; } return true; }优缺点：
优点：代码更简洁
缺点：需要额外的O(n)空间存储清洗后的字符串
2. 使用StringBuilder反转
public boolean isPalindromeWithBuilder(String s) { String cleaned = s.toLowerCase().replaceAll("[^a-z0-9]", ""); String reversed = new StringBuilder(cleaned).reverse().toString(); return cleaned.equals(reversed); }优缺点：
优点：代码极简
缺点：需要额外空间，且比较整个字符串
常见错误
错误1：忘记处理大小写
java
// 错误代码 if (s.charAt(i) == s.charAt(j)) { ... } // 应使用toLowerCase转换错误2：指针移动逻辑错误
java
// 错误代码：同时移动指针 if (!Character.isLetterOrDigit(s.charAt(i))) { i++; j--; // 错误：不应该同时移动j }错误3：边界条件处理不当
java
// 错误：没有考虑空字符串或全无效字符的情况 if (s.length() == 0) return false; // 应返回true
扩展思考
1. 如何修改代码以支持Unicode字符？
使用Character.isLetter()和Character.isDigit()分开判断：
java
if (!Character.isLetter(c) && !Character.isDigit(c)) { // 跳过 }2. 如何找到最长回文子串？
这是LeetCode第5题，可以使用动态规划或中心扩展法解决。
3. 如何统计字符串中的回文子串数量？
可以使用中心扩展法，统计以每个字符为中心的回文数量。
总结
验证回文串问题虽然简单，但涵盖了多个重要编程概念：
双指针技巧：高效的遍历方法
字符处理：大小写转换、字符类型判断
边界条件：空字符串、特殊字符处理
时间复杂度优化：O(n)时间复杂度和O(1)空间复杂度
掌握这个问题的解法不仅有助于通过面试，还能加深对字符串处理和算法优化的理解。
关键要点记忆：
使用双指针从两端向中间遍历
使用
Character.isLetterOrDigit()过滤无效字符使用
Character.toLowerCase()统一大小写注意边界条件的处理