双指针判断回文串方法详解

本文深入解析了利用双指针模式高效判断回文串的原理与应用。通过详细阐述 `while(left

本文深入探讨了如何利用双指针模式高效判断字符串是否为回文串。我们将详细解析 while(left < right) 循环条件的内在逻辑，阐明其如何巧妙地处理奇数和偶数长度的字符串，以及为何在奇数长度字符串中无需额外处理中间字符，确保算法的正确性和效率。

理解双指针模式与回文串检测

回文串是指一个正读反读都一样的字符串，例如 "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 < right) 循环条件

对于初学者来说，while(left < right) 这个循环条件可能会引起一些困惑，尤其是当字符串长度为奇数时，例如 "racecar"。当 left 和 right 指针最终都指向中间的 'e' 时，循环就会终止。那么，我们是如何确保没有“漏掉”中间的 'e' 呢？

关键在于理解回文串的定义和双指针的工作原理：

1. 偶数长度字符串：

   • 例如 "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)，循环终止。所有需要配对的字符都已成功比较。

2. 奇数长度字符串：

   • 例如 "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 < right) 确保了我们只比较那些需要进行配对检查的字符，当指针相遇或交叉时，意味着所有必要的配对都已完成。

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

虽然 while(left < right) 是最常用的条件，但有时你可能会看到 while(left <= right)。这两种条件的主要区别在于：

• while(left < right)： 循环在 left 和 right 指针相遇或交叉时停止。对于奇数长度字符串，中间的字符不会被检查（因为 left 和 right 会在中间字符的两侧停止，或者在下一轮迭代前相等）。这是最常见且推荐的做法，因为它避免了对中间字符的冗余检查。
• while(left <= right)： 循环会多执行一轮，直到 left 指针越过 right 指针。对于奇数长度字符串，当 left 和 right 都指向中间字符时，循环会执行最后一次，比较 processedStr[middle] 与 processedStr[middle]。虽然这不会影响结果，但它增加了一次不必要的比较操作。

因此，对于回文串判断，while(left < right) 是更简洁和高效的选择。

总结

双指针模式是解决回文串问题的强大工具。通过对字符串进行预处理，并利用 left 和 right 指针从两端向中间移动，我们可以高效地判断字符串是否为回文串。while(left < right) 循环条件是该模式的核心，它巧妙地处理了奇数和偶数长度字符串的差异，确保了只有需要配对的字符才会被比较，从而保证了算法的正确性和运行效率。理解其内在逻辑对于掌握双指针模式至关重要。

好了，本文到此结束，带大家了解了《双指针判断回文串方法详解》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多文章知识！