力扣刷题（第二十九天）

灵感来源 

- 保持更新，努力学习

- python脚本学习

验证回文串

解题思路

验证回文串的核心在于判断一个字符串是否从前向后和从后向前读都是一样的。不过，题目通常会有两个主要限制条件：

1. 忽略大小写：比如 "A man" 和 "a man" 被视为相同字符。
2. 只考虑字母和数字：需要过滤掉空格、标点符号等非字母数字字符。

最直接的方法是使用双指针法：

1. 预处理字符串：将字符串中的所有字母转为小写，并过滤掉非字母数字的字符。
2. 双指针遍历：使用两个指针，一个从字符串头部开始，一个从尾部开始，逐个比较字符是否相同。如果遇到不相同的字符，则返回 False；如果所有字符都相同，则返回 True。

这种方法的时间复杂度是 O(n)，其中 n 是字符串的长度，因为只需要遍历一次字符串。空间复杂度是 O(n)，主要用于存储预处理后的字符串。

class Solution:def isPalindrome(self, s: str) -> bool:# 过滤非字母数字字符并转换为小写filtered_chars = [c.lower() for c in s if c.isalnum()]# 双指针法验证回文串left, right = 0, len(filtered_chars) - 1while left < right:if filtered_chars[left] != filtered_chars[right]:return Falseleft += 1right -= 1return True

逐行解释

class Solution:def isPalindrome(self, s: str) -> bool:# 过滤非字母数字字符并转换为小写# isalnum() 方法检查字符是否为字母或数字# lower() 方法将字符转换为小写filtered_chars = [c.lower() for c in s if c.isalnum()]# 初始化左右指针，分别指向过滤后字符串的首尾left, right = 0, len(filtered_chars) - 1# 双指针遍历：当左指针小于右指针时继续循环while left < right:# 比较当前左右指针指向的字符if filtered_chars[left] != filtered_chars[right]:# 若不相等，直接返回 False（不是回文串）return False# 左指针右移一位left += 1# 右指针左移一位right -= 1# 所有字符均匹配，返回 True（是回文串）return True