验证回文串

🟢 Easy · 🏷️ 字符串、双指针 · LeetCode#125

📖 题目

判断字符串 s 是否是回文串——只看字母和数字，忽略大小写和其他字符。

输入	输出
"A man, a plan, a canal: Panama"	true

🆕 新知识

判断字符类型用 isalnum()：

c.isalnum()    # 是字母或数字
c.isalpha()    # 是字母
c.isdigit()    # 是数字

配合生成器表达式可以一行过滤：''.join(c for c in s if 条件)。

💡 思路

先把非字母数字字符过滤掉、统一转小写，再判断处理后的字符串是不是回文——切片反转 s[::-1] 最简单。

如果要省空间，可以用双指针从两端往中间逼近，遇到非字母数字就跳过，逐对比较，不需要额外存一份过滤后的字符串。

💻 代码

方法一：过滤 + 切片反转（推荐，代码简洁）

class Solution:
    def isPalindrome(self, s: str) -> bool:
        clean = ''.join(c for c in s.lower() if c.isalnum())
        return clean[::-1] == clean

时间复杂度 O(n)，空间复杂度 O(n)——多存了一份过滤后的字符串。

方法二：双指针（省空间）

class Solution:
    def isPalindrome(self, s: str) -> bool:
        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)。面试时可以先写方法一，再补一句"要优化空间可以用双指针"。