使用双指针模式判断回文串-小浪学习网

使用双指针模式判断回文串

本文详细介绍了如何利用双指针模式高效判断一个字符串是否为回文串。我们将探讨该模式的核心原理，包括字符串预处理、指针初始化及迭代过程。特别地，文章深入解析了 while(left

双指针模式判断回文串

回文串是指一个正读和反读都一样的字符串，例如“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)。