理解双指针模式与回文串检测
回文串是指一个正读反读都一样的字符串，例如 "racecar" 或 "madam"。双指针模式是解决这类问题的一种经典且高效的方法。其核心思想是设置两个指针，一个从字符串的起始位置（左端）开始，另一个从字符串的末尾位置（右端）开始，然后逐步向中间移动，同时比较两个指针所指向的字符。
在实现回文串检测时，我们通常需要先对输入字符串进行预处理，以确保比较的准确性。这包括将所有字符转换为小写（或大写），并移除所有非字母数字的字符。这样可以避免因大小写或标点符号差异而导致的错误判断。
以下是使用双指针模式判断回文串的典型实现：
/**
* 判断一个字符串是否为回文串
* @param {string} s 输入字符串
* @return {boolean} 如果是回文串则返回 true，否则返回 false
*/
var isPalindrome = function(s) {
// 预处理字符串：转换为小写并移除所有非字母数字字符
const processedStr = s.toLowerCase().replace(/[^0-9a-z]/g, "");
let left = 0; // 左指针，从字符串开头开始
let right = processedStr.length - 1; // 右指针，从字符串末尾开始
// 当左指针仍在右指针的左侧时，持续比较
while (left < right) {
// 如果左右指针指向的字符不相等，则不是回文串
if (processedStr[left] !== processedStr[right]) {
return false;
}
// 移动指针：左指针向右移动，右指针向左移动
left++;
right--;
}
// 如果循环结束都没有发现不匹配的字符，则是回文串
return true;
};
// 示例测试
console.log("racecar:", isPalindrome('racecar')); // true
console.log("Ceci n’est pas une palindrome:", isPalindrome('Ceci n’est pas une palindrome')); // false
console.log("A man, a plan, a canal: Panama:", isPalindrome('A man, a plan, a canal: Panama')); // true
console.log(" ", isPalindrome(' ')); // true深入理解 while(left
对于初学者来说，while(left
关键在于理解回文串的定义和双指针的工作原理：
-
偶数长度字符串：
- 例如 "abba"。
- 第一轮：left 指向 'a' (索引0)，right 指向 'a' (索引3)。匹配。left 变为 1，right 变为 2。
- 第二轮：left 指向 'b' (索引1)，right 指向 'b' (索引2)。匹配。left 变为 2，right 变为 1。
- 此时，left (2) 不再小于 right (1)，循环终止。所有需要配对的字符都已成功比较。
-
奇数长度字符串：
- 例如 "racecar"。
- 预处理后为 "racecar"。
- 第一轮：left 指向 'r' (索引0)，right 指向 'r' (索引6)。匹配。left 变为 1，right 变为 5。
- 第二轮：left 指向 'a' (索引1)，right 指向 'a' (索引5)。匹配。left 变为 2，right 变为 4。
- 第三轮：left 指向 'c' (索引2)，right 指向 'c' (索引4)。匹配。left 变为 3，right 变为 3。
- 此时，left (3) 不再小于 right (3)，循环终止。
为什么中间字符无需额外检查？
在奇数长度的字符串中，中间的字符（例如 "racecar" 中的 'e'）是独一无二的，它没有“对称”的另一半可以进行比较。一个字符本身总是“回文”的。因此，无论这个中间字符是什么，它都不会影响整个字符串是否为回文串的判断。只要其两侧对称位置的字符都匹配，那么整个字符串就是回文串。while(left
替代循环条件：while(left
虽然 while(left 区别在于：
- while(left 循环在 left 和 right 指针相遇或交叉时停止。对于奇数长度字符串，中间的字符不会被检查（因为 left 和 right 会在中间字符的两侧停止，或者在下一轮迭代前相等）。这是最常见且推荐的做法，因为它避免了对中间字符的冗余检查。
- while(left 循环会多执行一轮，直到 left 指针越过 right 指针。对于奇数长度字符串，当 left 和 right 都指向中间字符时，循环会执行最后一次，比较 processedStr[middle] 与 processedStr[middle]。虽然这不会影响结果，但它增加了一次不必要的比较操作。
因此，对于回文串判断，while(left
总结
双指针模式是解决回文串问题的强大工具。通过对字符串进行预处理，并利用 left 和 right 指针从两端向中间移动，我们可以高效地判断字符串是否为回文串。while(left
