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

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

双指针模式判断回文串

回文串是指一个正读和反读都一样的字符串，例如“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学习网公众号，一起学习编程~