LC125. 验证回文串

题目描述

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。 字母和数字都属于字母数字字符。 给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。 示例 1： 输入: s = "A man, a plan, a canal: Panama" 输出：true 解释："amanaplanacanalpanama" 是回文串。 示例 2： 输入：s = "race a car" 输出：false 解释："raceacar" 不是回文串。 示例 3： 输入：s = " " 输出：true 解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。 由于空字符串正着反着读都一样，所以是回文串。 提示： 1 <= s.length <= 2 * 10^5 s 仅由可打印的 ASCII 字符组成

题目解析

题目在说什么

这道题其实是在问：给你一个字符串，里面可能有乱七八糟的符号、空格、大小写字母和数字。你先把所有大写字母变成小写，然后只保留字母和数字（去掉标点、空格等），最后看看剩下的字符串正着读和反着读是不是一模一样。如果是，就返回 true，否则返回 false。

比如 "A man, a plan, a canal: Panama"，去掉非字母数字并转小写后变成 "amanaplanacanalpanama"，正着读和反着读一样，所以是回文串。而 "race a car" 处理后是 "raceacar"，反着读是 "racaecar"，不一样，所以不是。

思路是怎么来的

想象一下，你要判断一串字母是不是回文，最直接的办法就是：用两个手指头，一个从左边开始，一个从右边开始，同时往中间移动，每次比较两个手指指着的字母是否相同。如果所有字母都相同，就是回文。

但这里有个麻烦：字符串里混着空格、标点、大小写。所以你不能直接拿两个手指去比，因为可能左边手指指到一个空格，右边手指指到一个逗号，这些我们不想比。

所以思路就是：让两个手指跳过那些“无效”的字符（非字母数字），只比较“有效”的字符（字母和数字），并且比较时忽略大小写。

具体做法是：

• 用两个指针，一个 left 从字符串开头往右走，一个 right 从字符串结尾往左走。
• 当 left 指向的字符不是字母或数字时，left 就继续往右走（跳过它）。
• 当 right 指向的字符不是字母或数字时，right 就继续往左走（跳过它）。
• 当两个指针都指向字母或数字时，把它们都转成小写（或大写）后比较。如果不同，说明不是回文，直接返回 false。
• 如果相同，left 往右走一步，right 往左走一步，继续比较。
• 直到 left 和 right 相遇或者交叉，说明所有有效字符都相同，返回 true。

代码逐步拆解

我们来看一段 Python 代码（其他语言思路一样）：

def isPalindrome(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

逐步拆解：

1. left, right = 0, len(s) - 1

• 初始化两个指针，left 指向字符串第一个字符，right 指向最后一个字符。

2. while left < right:

• 只要左指针还在右指针左边，就继续比较。如果相遇或交叉，说明所有有效字符都比较完了。

3. while left < right and not s[left].isalnum():

• 这个内层循环的作用：如果 left 指向的字符不是字母或数字（isalnum() 返回 False），就不断把 left 往右移，直到找到第一个字母或数字，或者 left 和 right 相遇（防止越界）。