#验证回文串

#题目描述

给定一个字符串 s，验证它是否是回文串。

要求：

• 只考虑字母和数字字符，忽略其他字符（如空格、标点符号）。
• 忽略字母大小写。

#思路分析

题目的难点在于：字符串中混有空格、标点等无效字符，需要先屏蔽这些干扰，才能进行回文判断。

#预处理字符串的两种方式

#方式一：正则预清洗（生成新字符串）

用正则表达式一次性清洗原字符串，生成一个只含有效字符的新字符串，再对新字符串做回文判断：

const cleaned = s.replace(/[^a-z0-9]/gi, '').toLowerCase();

• /[^a-z0-9]/gi 匹配所有非字母、非数字的字符，replace 将它们全部替换为空字符串，从而只保留有效字符。
• .toLowerCase() 将字母统一转为小写，消除大小写差异。

经过这一步，"A man, a plan, a canal: Panama" 会变成 "amanaplanacanalpanama"，之后只需对新字符串做标准双指针比较即可，逻辑简洁清晰。

影响：提前分配了一个新字符串，空间复杂度为 O(n)；但循环体内逻辑最简单，可读性最高。

#方式二：isValid 辅助函数（原地跳过）

不提前清洗，而是在双指针循环内通过 isValid 函数实时判断字符是否有效，遇到无效字符就直接跳过：

const isValid = (char: string): boolean =>
    (char >= 'a' && char <= 'z') || (char >= '0' && char <= '9');

• 利用字符的字典序比较，'a' <= char <= 'z' 覆盖全部小写字母，'0' <= char <= '9' 覆盖全部数字。
• 需要配合 s.toLowerCase() 提前转小写，否则大写字母不在 'a'~'z' 范围内会被误判为无效字符。
• 双指针遇到无效字符时直接移动指针跳过，不需要额外的存储空间。

影响：无需生成新字符串，空间复杂度降低到 O(1)（仅 toLowerCase() 会产生新字符串，如果用 charCodeAt 判断则可完全避免）；但循环体内需要处理跳过逻辑，代码稍复杂。

#对比总结

#双指针比较

两种方式最终都用双指针从字符串两端向中间逼近，逐一比较对称位置的有效字符：

• 若某对字符不相等，直接返回 false。
• 两指针相遇时，说明所有对称位置均匹配，返回 true。

#算法步骤（以正则预清洗为例）

1. 用正则清洗字符串，去掉非字母数字字符并转为小写，得到 cleaned。
2. 初始化左指针 left = 0，右指针 right = cleaned.length - 1。
3. 当 left < right 时循环：
   • 若 cleaned[left] !== cleaned[right]，返回 false。
   • 否则，left++，right--。
4. 循环结束后返回 true。

#示例代码

/**
 * @param s - 待判断的字符串
 * @returns 若字符串满足回文条件则返回 true，否则返回 false
 *
 * @example
 * isPalindrome("A man, a plan, a canal: Panama") // true
 * isPalindrome("race a car") // false
 * isPalindrome(" ") // true
 */
export function isPalindrome(s: string): boolean {
    // 用正则去掉所有非字母数字字符，并统一转为小写，屏蔽大小写和标点符号的干扰。
    const cleaned = s.replace(/[^a-z0-9]/gi, '').toLowerCase();

    // 左指针从头部出发，右指针从尾部出发。
    let left = 0;
    let right = cleaned.length - 1;

    // 两指针向中间逼近，逐一比较对称位置的字符。
    while (left < right) {
        // 对称位置字符不相等，直接判定不是回文。
        if (cleaned[left] !== cleaned[right]) {
            return false;
        }
        left++;
        right--;
    }

    // 所有对称字符均匹配，是回文。
    return true;
}

/**
 * @param s - 待判断的字符串
 * @returns 若字符串满足回文条件则返回 true，否则返回 false
 *
 * @example
 * isPalindrome("A man, a plan, a canal: Panama") // true
 * isPalindrome("race a car") // false
 * isPalindrome(" ") // true
 */
export function isPalindrome(s: string): boolean {
    // 统一转为小写，方便后续 isValid 只需覆盖 'a'~'z' 范围
    s = s.toLowerCase();

    /**
     * 判断一个字符是否为有效字符（小写字母或数字）。
     * 利用字符的字典序比较，无需正则，也不产生新字符串。
     */
    const isValid = (char: string): boolean =>
        (char >= 'a' && char <= 'z') || (char >= '0' && char <= '9');

    // 左指针从字符串头部出发
    let left = 0;
    // 右指针从字符串尾部出发
    let right = s.length - 1;

    // 两指针未相遇时持续循环
    while (left < right) {
        const lChar = s[left];
        const rChar = s[right];

        // 左侧字符无效，跳过并右移左指针
        if (!isValid(lChar)) {
            left++;
            continue;
        }

        // 右侧字符无效，跳过并左移右指针
        if (!isValid(rChar)) {
            right--;
            continue;
        }

        // 两侧字符均有效，若不相等则不是回文，立即返回 false
        if (lChar !== rChar) {
            return false;
        }

        // 当前这对字符匹配，继续向中间移动
        left++;
        right--;
    }

    // 所有有效字符均两两匹配，是回文
    return true;
}

#复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串长度。正则清洗和双指针遍历各一次线性操作。
• 空间复杂度：O(n)，清洗后的字符串 cleaned 需要额外空间存储。

#示例演示

以 s = "A man, a plan, a canal: Panama" 为例：

第一步：正则清洗

第二步：双指针比较

所有对称字符均相等，最终返回 true。

以 s = "race a car" 为例，清洗后得到 "raceacar"：

第 4 轮字符不相等，直接返回 false。