双指针法判断回文串技巧分享

本文深入解析了使用双指针法高效判断回文串的技巧，该方法是解决字符串是否正反相同的经典算法。文章详细阐述了双指针模式的核心原理，包括字符串预处理（忽略大小写和非字母数字字符）、指针初始化以及`while(left

本文详细介绍了如何利用双指针模式高效判断一个字符串是否为回文串。我们将探讨该模式的核心原理，包括字符串预处理、指针初始化及迭代过程。特别地，文章深入解析了 while(left < right) 循环条件在处理奇数和偶数长度字符串时的有效性，并解释了为何无需显式检查中间字符。通过示例代码和注意事项，读者将全面掌握这一经典算法模式。

双指针模式判断回文串

回文串是指一个正读和反读都一样的字符串，例如“level”、“racecar”或“上海自来水来自海上”。在计算机科学中，判断一个字符串是否为回文串是一个常见的问题。双指针模式（Two Pointers Pattern）是解决此类问题的一种高效且直观的方法。

1. 双指针模式核心原理

双指针模式通过在数据结构的两端或特定位置设置两个指针，然后根据特定条件向中间或特定方向移动，以完成遍历、比较或操作。对于回文串判断，其基本思想是：

1. 初始化两个指针，一个指向字符串的起始位置（左指针 left），另一个指向字符串的末尾位置（右指针 right）。
2. 在两个指针相遇或交叉之前，不断比较它们所指向的字符。
3. 如果任意一对字符不匹配，则该字符串不是回文串。
4. 如果所有字符对都匹配，直到指针相遇或交叉，则该字符串是回文串。

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 < right) 循环条件

原始问题中提到了对 while(left < right) 循环条件的疑问，特别是对于奇数长度字符串（如 'racecar'）是否会“遗漏”中间字符。这里我们详细解释其工作原理：

• 核心逻辑： 判断回文串的关键在于，字符串前半部分的字符是否与后半部分对应位置的字符对称相等。中间的字符（如果字符串长度为奇数）自身没有对称的配对字符，因此其值不影响回文性。
• 偶数长度字符串（例如 '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 < right) 条件确保了我们只比较需要配对的字符。当 left 指针和 right 指针相遇或交叉时，所有必要的对称比较都已经完成。对于奇数长度的字符串，中间的字符是它自己，无需进行额外的比较。

5. 替代循环条件 while(left <= right)

如果将循环条件改为 while(left <= right)，对于奇数长度字符串，循环会多执行一次，将中间字符与自身进行比较。例如对于 'racecar'，当 left 和 right 都指向 'e' 时，left <= right 仍然为真，会执行一次 cleanedStr[3] === cleanedStr[3] 的比较。这虽然不会影响结果的正确性，但多了一次不必要的比较操作。因此，在大多数情况下，while(left < right) 是更简洁和高效的选择。

6. 注意事项与优化

• 空字符串和单字符字符串： 根据回文串的定义，空字符串和只包含一个字符的字符串通常被认为是回文串。上述代码能够正确处理这些情况。
• 时间复杂度： 字符串预处理的时间复杂度取决于字符串长度 N 和正则表达式的复杂性，通常为 O(N)。双指针遍历的时间复杂度为 O(N/2)，即 O(N)。因此，总的时间复杂度为 O(N)。
• 空间复杂度： replace() 方法会创建一个新的字符串 cleanedStr，因此空间复杂度为 O(N)。如果允许修改原始字符串或使用双指针直接在原始字符串上操作（但需要额外逻辑跳过非字母数字字符），则空间复杂度可以优化到 O(1)。

总结

双指针模式是解决回文串判断问题的有效方法。通过在字符串两端设置指针并向内移动，我们可以高效地比较对称位置的字符。理解 while(left < right) 循环条件对于正确处理奇数和偶数长度字符串至关重要，它避免了不必要的比较，使得算法既正确又高效。掌握这一模式不仅能解决回文串问题，也能为解决其他需要双向遍历或配对比较的算法问题提供思路。

今天带大家了解了的相关知识，希望对你有所帮助；关于文章的技术知识我们会一点点深入介绍，欢迎大家关注golang学习网公众号，一起学习编程~