Valid Palindrome（验证回文串）

题目 / Problem

中文： 如果一个短语在将所有大写字母转换为小写字母，并删除所有非字母数字字符后，正着读和反着读都相同，那么它就是回文串。字母数字字符包括英文字母和数字。

给定一个字符串 s，如果它是回文串，返回 true；否则返回 false。

English: A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

示例 / Examples

Example 1

Input:  s = "A man, a plan, a canal: Panama"
Output: true

解释 / Explanation:
处理后的字符串为 "amanaplanacanalpanama"，它是回文串。
After processing, the string is "amanaplanacanalpanama", which is a palindrome.

Example 2

Input:  s = "race a car"
Output: false

解释 / Explanation:
处理后的字符串为 "raceacar"，它不是回文串。
After processing, the string is "raceacar", which is not a palindrome.

Example 3

Input:  s = " "
Output: true

解释 / Explanation:
删除非字母数字字符后，s 变成空字符串 ""。
After removing non-alphanumeric characters, s becomes the empty string "".

空字符串正着读和反着读都相同，因此它是回文串。
An empty string reads the same forward and backward, so it is a palindrome.

约束 / Constraints

1 <= s.length <= 2 × 10⁵
s 仅由可打印的 ASCII 字符组成。
s consists only of printable ASCII characters.

解题思路：双指针 / Approach: Two Pointers

使用两个指针分别从字符串的两端向中间移动：
Use two pointers that move inward from opposite ends of the string:

left 从字符串开头向右移动。
left moves right from the beginning.
right 从字符串末尾向左移动。
right moves left from the end.

处理过程如下：
The process is as follows:

如果 left 指向的字符不是字母或数字，跳过它。
If the character at left is not alphanumeric, skip it.
如果 right 指向的字符不是字母或数字，同样跳过它。
If the character at right is not alphanumeric, skip it as well.
将两端的有效字符转换为小写并比较。
Convert the valid characters at both ends to lowercase and compare them.
如果字符不同，立即返回 false；否则继续向中间移动。
If they differ, return false immediately; otherwise, continue moving inward.
如果两个指针相遇或交错，说明所有字符都匹配，返回 true。
If the pointers meet or cross, every character matched, so return true.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {string} s
 * @return {boolean}
 */
function isPalindrome(s) {
  let left = 0;
  let right = s.length - 1;

  const isAlphanumeric = (char) => /[a-zA-Z0-9]/.test(char);

  while (left < right) {
    while (left < right && !isAlphanumeric(s[left])) {
      left++;
    }

    while (left < right && !isAlphanumeric(s[right])) {
      right--;
    }

    if (s[left].toLowerCase() !== s[right].toLowerCase()) {
      return false;
    }

    left++;
    right--;
  }

  return true;
}

执行过程 / Walkthrough

以 s = "A man, a plan, a canal: Panama" 为例。忽略非字母数字字符并忽略大小写后，双指针依次比较：
For s = "A man, a plan, a canal: Panama", after ignoring non-alphanumeric characters and letter case, the pointers compare:

a ↔ a
m ↔ m
a ↔ a
n ↔ n
a ↔ a
p ↔ p
l ↔ l
a ↔ a
n ↔ n
a ↔ a
c ↔ c
a ↔ a
n ↔ n
a ↔ a
l ↔ l

所有对应字符都相同，因此返回 true。
Every corresponding pair matches, so the function returns true.

复杂度 / Complexity

时间复杂度：O(n)，每个字符最多被检查一次。
Time: O(n), because each character is examined at most once.
空间复杂度：O(1)，双指针解法不需要创建处理后的新字符串。
Space: O(1), because the two-pointer approach does not create a processed copy of the string.

简化解法 / Concise Approach

也可以先删除非字母数字字符并统一转换为小写，再将字符串与它的反转结果进行比较：
Alternatively, remove non-alphanumeric characters, convert the result to lowercase, and compare it with its reversed form:

function isPalindromeConcise(s) {
  const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, '');
  return cleaned === [...cleaned].reverse().join('');
}

时间复杂度 / Time: O(n)
空间复杂度 / Space: O(n)，需要保存清理和反转后的字符串。
Extra space is required for the cleaned and reversed strings.

双指针解法的额外空间复杂度更低，更适合作为本题的最优解。
The two-pointer solution uses less extra space and is the preferred solution for this problem.

易错点 / Common Pitfalls

比较前必须忽略标点符号、空格和其他非字母数字字符。
Ignore punctuation, spaces, and other non-alphanumeric characters before comparison.
比较时不区分英文字母的大小写。
Letter comparisons must be case-insensitive.
数字也是有效字符，不能将它们过滤掉。
Digits are valid characters and must not be removed.
清理后得到的空字符串也属于回文串。
An empty string produced after cleaning is also a palindrome.
双指针跳过无效字符时，要避免指针越界或重复比较。
When skipping invalid characters, avoid moving pointers out of bounds or comparing characters twice.

Valid Palindrome