回文串与双指针模式概述
回文串是指一个正读和反读都相同的字符串，例如 "racecar" 或 "level"。在计算机科学中，检测一个字符串是否为回文串是常见的算法问题。双指针模式（two pointers pattern）是解决这类问题的一种高效且直观的方法。该模式通过在数据结构（如字符串、数组）的两端或特定位置设置两个指针，然后根据特定条件向中间或特定方向移动，从而实现对数据的遍历、比较或操作。对于回文串检测，我们通常将一个指针置于字符串的起始位置，另一个指针置于末尾位置，然后逐步向字符串中心移动，同时比较指针所指的字符。
核心实现：字符串预处理与指针初始化
在进行回文串检测之前，通常需要对输入字符串进行预处理，以确保比较的准确性和一致性。这主要包括以下两点：
- 转换为小写： 忽略大小写差异，确保 'A' 和 'a' 被视为相同的字符。
- 移除非字母数字字符： 忽略标点符号、空格等非字母数字字符，只比较构成回文的核心字符。
预处理完成后，我们将初始化两个指针：
- left 指针：指向处理后字符串的起始位置（索引 0）。
- right 指针：指向处理后字符串的末尾位置（索引 length - 1）。
var isPalindrome = function(s) {
// 1. 字符串预处理：转换为小写并移除所有非字母数字字符
const newStr = s.toLowerCase().replace(/[^0-9a-z]/g, "");
// 2. 初始化双指针
let left = 0;
let right = newStr.length - 1;
// ... 后续逻辑
};循环条件 while(left
双指针模式的核心在于其循环条件。对于回文串检测，最常见的条件是 while (left
1. 偶数长度字符串示例：以 "level" 为例
假设预处理后的字符串为 "level"：
- 初始状态：left = 0 (l), right = 4 (l)
-
第一次迭代：
- newStr[0] ('l') === newStr[4] ('l')，匹配。
- left 增至 1 (e)，right 减至 3 (e)。
- 当前状态：left = 1, right = 3
-
第二次迭代：
- newStr[1] ('e') === newStr[3] ('e')，匹配。
- left 增至 2 (v)，right 减至 2 (v)。
- 当前状态：left = 2, right = 2
- 循环结束： 此时 left 不再小于 right (2
2. 奇数长度字符串示例：以 "racecar" 为例
假设预处理后的字符串为 "racecar"：
- 初始状态：left = 0 (r), right = 6 (r)
-
第一次迭代：
- newStr[0] ('r') === newStr[6] ('r')，匹配。
- left 增至 1 (a)，right 减至 5 (a)。
- 当前状态：left = 1, right = 5
-
第二次迭代：
- newStr[1] ('a') === newStr[5] ('a')，匹配。
- left 增至 2 (c)，right 减至 4 (c)。
- 当前状态：left = 2, right = 4
-
第三次迭代：
- newStr[2] ('c') === newStr[4] ('c')，匹配。
- left 增至 3 (e)，right 减至 3 (e)。
- 当前状态：left = 3, right = 3
- 循环结束： 此时 left 不再小于 right (3
为什么 while(left
在奇数长度字符串中，会有一个位于正中间的字符（例如 "racecar" 中的 'e'）。当 left 和 right 指针最终相遇或交叉时，这意味着所有成对的字符都已经成功比较完毕。中间的那个字符由于没有配对的字符，它必然是和自身相等的，因此无需显式地进行比较。while(left
完整示例代码
结合上述分析，完整的双指针回文串检测函数如下：
var isPalindrome = function(s) {
// 1. 字符串预处理：转换为小写并移除所有非字母数字字符
const newStr = s.toLowerCase().replace(/[^0-9a-z]/g, "");
// 2. 初始化双指针
let left = 0;
let right = newStr.length - 1;
// 3. 循环比较，直到左右指针相遇或交叉
while (left < right) {
// 如果左右指针所指字符不相等，则不是回文串
if (newStr[left] !== newStr[right]) {
return false;
}
// 移动指针向中间靠拢
left++;
right--;
}
// 如果循环结束都没有返回 false，则说明是回文串
return true;
};
// 测试用例
console.log(isPalindrome('racecar')); // 输出: true
console.log(isPalindrome('A man, a plan, a canal: Panama')); // 输出: true
console.log(isPalindrome('Ceci n’est pas une palindrome')); // 输出: false
console.log(isPalindrome('level')); // 输出: true替代方案：while(left
有时，你可能会看到循环条件使用 while(left
例如，对于 "racecar"，当 left = 3, right = 3 时，3
选择建议：
- while(left 这是更推荐和高效的方式，因为它只执行必要的比较。对于中间字符，它自身总是匹配的，无需额外检查。
- while(left 也可以工作，但会多一次不必要的比较（对于奇数长度字符串）。在某些特殊场景下，如果需要确保即使是单个字符也经过循环体处理，可能会选择这种方式，但对于标准的回文检测，通常不是必需的。
注意事项与总结
- 字符串预处理的重要性： 忽略大小写和非字母数字字符是确保回文检测逻辑健壮性的关键。
- 时间复杂度： 双指针模式的回文检测算法的时间复杂度为 O(N)，其中 N 是字符串的长度，因为我们只需要遍历字符串大约一半的长度。字符串预处理可能也需要 O(N) 时间。
- 空间复杂度： 如果创建一个新的字符串进行预处理，空间复杂度为 O(N)。如果选择原地处理（例如，在某些语言中），则可以优化到 O(1) 的空间复杂度（不考虑递归栈）。
- 适用性： 双指针模式不仅适用于回文串检测，在数组排序、查找配对元素、链表操作等多种场景中都有广泛应用。
通过本文的深入解析，相信读者已对双指针模式在回文串检测中的应用有了清晰的理解，特别是 while(left
