双指针模式判断回文串
回文串是指一个正读和反读都一样的字符串，例如“level”、“racecar”或“上海自来水来自海上”。在计算机科学中，判断一个字符串是否为回文串是一个常见的问题。双指针模式（two pointers pattern）是解决此类问题的一种高效且直观的方法。
1. 双指针模式核心原理
双指针模式通过在数据结构的两端或特定位置设置两个指针，然后根据特定条件向中间或特定方向移动，以完成遍历、比较或操作。对于回文串判断，其基本思想是：
- 初始化两个指针，一个指向字符串的起始位置（左指针 left），另一个指向字符串的末尾位置（右指针 right）。
- 在两个指针相遇或交叉之前，不断比较它们所指向的字符。
- 如果任意一对字符不匹配，则该字符串不是回文串。
- 如果所有字符对都匹配，直到指针相遇或交叉，则该字符串是回文串。
2. 字符串预处理
在进行回文串判断之前，通常需要对原始字符串进行预处理，以确保比较的准确性。这主要包括两个方面：
- 忽略大小写： 将所有字符转换为统一的大小写（通常是小写），例如 'Racecar' 和 'racecar' 都应被视为回文串。
- 忽略非字母数字字符： 移除字符串中的空格、标点符号或其他特殊字符，只保留字母和数字进行比较。例如 'A man, a plan, a canal: Panama' 在预处理后应变为 'amanaplanacanalpanama'。
预处理可以通过正则表达式和字符串方法实现。
3. 代码实现与解析
以下是使用 JavaScript 实现双指针模式判断回文串的示例代码：
/**
* 判断一个字符串是否为回文串
* @param {string} s 输入字符串
* @return {boolean} 是否为回文串
*/
var isPalindrome = function(s) {
// 1. 预处理字符串：转换为小写并移除所有非字母数字字符
const cleanedStr = s.toLowerCase().replace(/[^0-9a-z]/g, "");
// 2. 初始化双指针
let left = 0; // 左指针，指向字符串开头
let right = cleanedStr.length - 1; // 右指针，指向字符串末尾
// 3. 遍历比较：当左指针小于右指针时继续循环
while (left < right) {
// 如果左右指针指向的字符不相等，则不是回文串
if (cleanedStr[left] !== cleanedStr[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('')); // true (空字符串是回文串)
console.log(isPalindrome('a')); // true (单个字符是回文串)4. 深入理解 while(left
原始问题中提到了对 while(left
- 核心逻辑： 判断回文串的关键在于，字符串前半部分的字符是否与后半部分对应位置的字符对称相等。中间的字符（如果字符串长度为奇数）自身没有对称的配对字符，因此其值不影响回文性。
-
偶数长度字符串（例如 'abba'）：
- 初始：left = 0 (a), right = 3 (a)
- 第一次循环：cleanedStr[0] ('a') == cleanedStr[3] ('a')。left 变为 1, right 变为 2。
- 第二次循环：left = 1 (b), right = 2 (b)。cleanedStr[1] ('b') == cleanedStr[2] ('b')。left 变为 2, right 变为 1。
- 此时 left (2) 不再小于 right (1)，循环终止。所有配对字符都已检查完毕。
-
奇数长度字符串（例如 'racecar'）：
- 初始：left = 0 (r), right = 6 (r)
- 第一次循环：cleanedStr[0] ('r') == cleanedStr[6] ('r')。left 变为 1, right 变为 5。
- 第二次循环：left = 1 (a), right = 5 (a)。cleanedStr[1] ('a') == cleanedStr[5] ('a')。left 变为 2, right 变为 4。
- 第三次循环：left = 2 (c), right = 4 (c)。cleanedStr[2] ('c') == cleanedStr[4] ('c')。left 变为 3, right 变为 3。
- 此时 left (3) 不再小于 right (3)，循环终止。中间字符 'e'（索引 3）没有被显式比较，但这是正确的，因为回文性不依赖于中间字符与自身的比较。
总结： while(left
5. 替代循环条件 while(left
如果将循环条件改为 while(left
6. 注意事项与优化
- 空字符串和单字符字符串： 根据回文串的定义，空字符串和只包含一个字符的字符串通常被认为是回文串。上述代码能够正确处理这些情况。
- 时间复杂度： 字符串预处理的时间复杂度取决于字符串长度 N 和正则表达式的复杂性，通常为 O(N)。双指针遍历的时间复杂度为 O(N/2)，即 O(N)。因此，总的时间复杂度为 O(N)。
- 空间复杂度： replace() 方法会创建一个新的字符串 cleanedStr，因此空间复杂度为 O(N)。如果允许修改原始字符串或使用双指针直接在原始字符串上操作（但需要额外逻辑跳过非字母数字字符），则空间复杂度可以优化到 O(1)。
总结
双指针模式是解决回文串判断问题的有效方法。通过在字符串两端设置指针并向内移动，我们可以高效地比较对称位置的字符。理解 while(left
