0125.验证回文串
难度：🟢 简单
标签：双指针、字符串
链接：125. 验证回文串
题目描述
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样，则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 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 是一个空字符串 "" 。由于空字符串正着反着读都一样，所以是回文串。
解题思路
核心思想
本题的核心是在判断回文串之前，先对原始字符串进行“清洗”。我们需要忽略所有非字母和非数字的字符（如空格、标点符号），并且在比较时忽略字母的大小写。
思路选择
双指针法 是解决此问题的最优思路。
我们设置两个指针，
left和right，分别从字符串的头部和尾部开始。两个指针同时向中间移动。在移动过程中，如果遇到非字母数字字符，就跳过它。
当两个指针都指向有效的字母数字字符时，就将它们转换为小写并进行比较。如果不相等，则该字符串不是回文串。如果相等，则继续向中间移动。
当
left指针越过right指针时，说明所有有效的字符都已比较完毕且匹配，该字符串是回文串。
关键步骤
初始化：创建两个指针，
left = 0，right = s.length - 1。循环比较：当
left < right时，持续循环。 a. 移动左指针：如果s[left]不是有效字符，则left++，继续下一轮循环。 b. 移动右指针：如果s[right]不是有效字符，则right--，继续下一轮循环。 c. 比较字符：当左右指针都指向有效字符时，将它们都转换为小写进行比较。如果s[left].toLowerCase() !== s[right].toLowerCase()，则立即返回false。 d. 收缩范围：如果字符相等，则将两个指针向中间移动，left++，right--。返回结果：如果循环正常结束，说明字符串是回文的，返回
true。
代码实现 (推荐)
/**
* @param {string} s
* @return {boolean}
*/
var isPalindrome = function (s) {
let left = 0, right = s.length - 1;
const reg = /^[a-zA-Z0-9]$/; // 正则表达式用于验证字母数字字符
while (left < right) {
// 从左边找到第一个有效字符
if (!reg.test(s[left])) {
left++;
continue;
}
// 从右边找到第一个有效字符
if (!reg.test(s[right])) {
right--;
continue;
}
// 比较两个有效字符（忽略大小写）
if (s[left].toLowerCase() !== s[right].toLowerCase()) {
return false;
}
// 移动指针
left++;
right--;
}
return true;
};
原始代码分析 (用户提供)
您提供的解法逻辑完全正确，通过一个辅助函数来判断字符有效性，思路清晰。
// 辅助函数，判断字符是否为字母或数字
var isValidChar = function (str) {
return (str <= 'Z' && str >= 'A') || (str <= 'z' && str >= 'a') || (str <= '9' && str >= '0');
}
/**
* @param {string} s
* @return {boolean}
*/
var isPalindrome = function (s) {
let left = 0, right = s.length - 1;
// 主循环，当左指针在右指针左边或重合时
while (left <= right) {
// 内循环，跳过左边的无效字符
while (!isValidChar(s[left]) && left <= right) {
left++;
}
// 内循环，跳过右边的无效字符
while (!isValidChar(s[right]) && left <= right) {
right--;
}
// 再次检查指针是否越界
if (left <= right) {
// 比较并移动指针
if (s[left].toLowerCase() === s[right].toLowerCase()) {
left++;
right--;
} else return false;
}
}
return true;
};
优点：逻辑正确，并且将字符验证的逻辑封装在辅助函数中，代码结构清晰。
潜在优化点：代码中使用了嵌套的
while循环，虽然功能正确，但可读性上可以稍作调整。推荐解法中使用continue将逻辑扁平化在单个while循环内，有时会更易于理解。
复杂度分析
时间复杂度：O(n) 其中 n 是字符串
s的长度。双指针最多遍历整个字符串一次。空间复杂度：O(1) 我们只使用了常数个额外变量。
相关题目
总结
本题是双指针技巧的经典应用。通过“从两端向中间”的策略，并结合适当的过滤条件，可以非常高效地解决回文判断问题。这种处理字符串（或数组）两端关系的模式非常常用。