核心内容摘要
红桃17c·c18起草
问题描述在编程面试中验证回文串是一个经典问题。
题目要求我们判断一个字符串是否为回文串但有两个特殊要求只考虑字母和数字字符忽略字符的大小写示例 1text输入: A man, a plan, a canal: Panama 输出: true 解释: amanaplanacanalpanama 是回文串示例 2text输入: race a car 输出: false 解释: raceacar 不是回文串什么是回文串回文串是指正着读和反着读都一样的字符串。
例如levelradar上海自来水来自海上解决双指针法核心思想使用两个指针从字符串的两端向中间移动逐步比较字符是否相同。
算法步骤初始化指针左指针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; // 所有字符匹配 } }算法详解关键方法解析
Character.isLetterOrDigit(char ch)这个方法用于判断字符是否为字母或数字字母A-Z, a-z数字
其他字符标点、空格等返回false
Character.toLowerCase(char ch)将字符转换为小写大写字母A → a小写字母和数字保持不变确保大小写不敏感的比较复杂度分析时间复杂度O(n)n是字符串的长度每个字符最多被访问一次左指针或右指针最坏情况下需要遍历整个字符串空间复杂度O(
只使用了常数级别的额外空间只存储了两个指针和几个临时变量优化技巧
预处理字符串备选方案可以先清洗字符串再判断public boolean isPalindromeAlternative(String s) { //
转换为小写 //
移除非字母数字字符 String cleaned s.toLowerCase().replaceAll([^a-z
], ); //
判断清洗后的字符串是否为回文 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)空间存储清洗后的字符串
使用StringBuilder反转public boolean isPalindromeWithBuilder(String s) { String cleaned s.toLowerCase().replaceAll([^a-z
], ); 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()
return false; // 应返回true扩展思考
如何修改代码以支持Unicode字符使用Character.isLetter()和Character.isDigit()分开判断javaif (!Character.isLetter(c) !Character.isDigit(c)) { // 跳过 }
如何找到最长回文子串这是LeetCode第5题可以使用动态规划或中心扩展法解决。
如何统计字符串中的回文子串数量可以使用中心扩展法统计以每个字符为中心的回文数量。
总结验证回文串问题虽然简单但涵盖了多个重要编程概念双指针技巧高效的遍历方法字符处理大小写转换、字符类型判断边界条件空字符串、特殊字符处理时间复杂度优化O(n)时间复杂度和O(
空间复杂度掌握这个问题的解法不仅有助于通过面试还能加深对字符串处理和算法优化的理解。
关键要点记忆使用双指针从两端向中间遍历使用Character.isLetterOrDigit()过滤无效字符使用Character.toLowerCase()统一大小写注意边界条件的处理