LeetCode 125. 验证回文串

◎

本节目标

在忽略非字母数字字符和大小写后，用双指针验证字符串是否回文。

这道题使用字符串基础解题框架的相向扫描。题目比较的是过滤后的、忽略大小写的字符序列，不是原始字符串的每一个位置。

查看原题

朴素思路及瓶颈

可以先构造一个只含字母数字的小写副本，再与它的反转串比较。该方法是线性的，但额外复制了整个有效序列；如果在原串上直接跳过无关字符，就能把空间降到常数级。

相向扫描不变量

左右指针之间是尚未判断的区间。每轮先跳过非字母数字字符，再比较两端有效字符的小写形式；若相等，同时向内收缩。空串或全是空白、标点的字符串没有反例，按题意应返回真。C++ 中字符分类和大小写转换前先转 unsigned char，避免负值 char 传给 cctype 函数。

代码实现

两份源码都在原字符串上扫描，不创建过滤副本。Python 使用字符串的字符方法；C++ 在调用 isalnum 和 tolower 时显式进行安全转换。

C++

C++17

#include <cctype>
#include <string>
using namespace std;

class Solution {
public:
    bool isPalindrome(string s) {
        int left = 0;
        int right = static_cast<int>(s.size()) - 1;

        while (left < right) {
            while (left < right && !isalnum(static_cast<unsigned char>(s[left]))) {
                left++;
            }
            while (left < right && !isalnum(static_cast<unsigned char>(s[right]))) {
                right--;
            }
            if (tolower(static_cast<unsigned char>(s[left])) !=
                tolower(static_cast<unsigned char>(s[right]))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};

Python

Python 3

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left = 0
        right = 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)。

易错点

• 只在比较前跳过一端的标点，导致另一端仍与无关字符比较。
• 跳过字符后不检查指针是否已经相遇。
• 忽略大小写规则，或在 C++ 中把带符号 char 直接交给字符分类函数。

模式迁移

同样的双指针可用于“至多删除一个字符的回文”以及两个已规范化序列的比较。若必须保留过滤后的结果，再采用构造副本的方式；重点仍是明确哪些字符属于比较对象。