力扣经典150题解析之二十五：验证回文串
1. 介绍
在这篇文章中，我们将解析力扣经典150题中的第二十五题：验证回文串。给定一个字符串 s，如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，该字符串正着读和反着读都一样，则认为它是一个回文串。
2. 问题描述
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
3. 示例
示例 1:
输入: s = "A man, a plan, a canal: Panama" 输出：true 解释："amanaplanacanalpanama" 是回文串。
示例 2:
输入：s = "race a car" 输出：false 解释："raceacar" 不是回文串。
示例 3:
输入：s = " " 输出：true 解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。 由于空字符串正着反着读都一样，所以是回文串。
4. 解题思路
我们可以使用双指针的方法来解决这个问题：
- 首先将字符串 s 转换为小写字母。
- 使用两个指针，一个指向字符串开头，一个指向字符串末尾，逐步向中间移动。
- 每次移动时，跳过非字母数字字符，只比较字母数字字符是否相同。
- 如果找到不相同的字符，返回 false，否则直到两个指针相遇时都没有找到不同的字符，则返回 true。
5. 代码实现
public class Solution { public boolean isPalindrome(String s) { int left = 0; int right = s.length() - 1; while (left < right) { while (left < right && !Character.isLetterOrDigit(s.charAt(left))) { left++; } while (left < right && !Character.isLetterOrDigit(s.charAt(right))) { right--; } char leftChar = Character.toLowerCase(s.charAt(left)); char rightChar = Character.toLowerCase(s.charAt(right)); if (leftChar != rightChar) { return false; } left++; right--; } return true; } }
6. 复杂度分析
- 时间复杂度：O(n)，其中 n 是字符串 s 的长度。双指针遍历一次字符串。
- 空间复杂度：O(1)，只使用了常数级别的额外空间。
7. 测试与验证
我们对示例输入进行测试：
public class Main { public static void main(String[] args) { Solution solution = new Solution(); String s1 = "A man, a plan, a canal: Panama"; System.out.println("是否是回文串：" + solution.isPalindrome(s1)); // 输出 true String s2 = "race a car"; System.out.println("是否是回文串：" + solution.isPalindrome(s2)); // 输出 false String s3 = " "; System.out.println("是否是回文串：" + solution.isPalindrome(s3)); // 输出 true } }
8. 总结
通过使用双指针遍历字符串并比较字符，我们可以有效地判断一个字符串是否是回文串。在遍历过程中，跳过非字母数字字符，只比较字母数字字符的小写形式是否相同。
9. 扩展
我们可以探讨一些扩展话题，例如使用其他方法（如正则表达式）来解决字符串处理的问题，或者讨论特殊情况和边界条件下的处理方式。
希望本文能够帮助读者理解回文串的概念及其判断方法。
