LeetCode 125. Valid Palindrome 题解
LeetCode 125. Valid Palindrome 题解
题目描述
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
示例 1：
输入: "A man, a plan, a canal: Panama" 输出: true 解释："amanaplanacanalpanama" 是回文串示例 2：
输入: "race a car" 输出: false 解释："raceacar" 不是回文串解题思路
双指针法：
- 使用左右指针分别从字符串的两端向中间移动
- 跳过非字母和数字的字符
- 比较左右指针指向的字符（忽略大小写）
代码实现
def isPalindrome(s): left, right = 0, len(s) - 1 while left < right: # 跳过非字母和数字的字符 while left < right and not s[left].isalnum(): left += 1 while left < right and not s[right].isalnum(): right -= 1 # 比较字符（忽略大小写） if s[left].lower() != s[right].lower(): return False left += 1 right -= 1 return True复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
测试案例
# 测试案例 1 assert isPalindrome("A man, a plan, a canal: Panama") == True # 测试案例 2 assert isPalindrome("race a car") == False # 测试案例 3 assert isPalindrome("") == True # 测试案例 4 assert isPalindrome("a") == True总结
本题是字符串处理的经典问题。
关键点：
- 双指针技巧
- 字符类型判断
- 大小写处理
- 边界条件处理
通过本题可以深入理解双指针在字符串处理中的应用。