回文串检测：双指针算法详解与边界处理

核心原理：双指针法检测回文串

回文串是指一个正读和反读都一样的字符串。例如，“racecar”和“madam”都是回文串。双指针法是解决这类问题的一种高效策略，其基本思想是从字符串的两端同时向中间移动两个指针（一个从左向右，一个从右向左），并比较它们所指向的字符是否相同。如果所有对应的字符都相同，则该字符串是回文串；否则，则不是。

在实际应用中，通常需要对输入字符串进行预处理，以忽略大小写和非字母数字字符，确保比较的准确性。

while (left < right) 条件的深层理解

在双指针算法中，while (left < right) 是最常用的循环条件。这个条件确保了只要左指针仍在右指针的左侧，比较就会继续进行。一旦 left 指针与 right 指针相遇或交叉，循环就会终止。

很多初学者可能会对奇数长度字符串（如“racecar”）的处理感到困惑，担心中间的字符（如“e”）是否会被遗漏，从而影响判断的准确性。实际上，while (left < right) 这种条件是完全正确的，并且足以判断回文串：

1. 偶数长度字符串：例如“abba”。

   • 初始：left 指向 'a' (索引0)，right 指向 'a' (索引3)。
   • 第一次循环：left 指向 'a'，right 指向 'a'。两者相等。left 变为1，right 变为2。
   • 第二次循环：left 指向 'b'，right 指向 'b'。两者相等。left 变为2，right 变为1。
   • 此时 left (2) 不再小于 right (1)，循环终止。由于所有比较的字符都相等，返回 true。

2. 奇数长度字符串：例如“racecar”。

   • 初始：left 指向 'r' (索引0)，right 指向 'r' (索引6)。
   • 第一次循环：left 指向 'r'，right 指向 'r'。两者相等。left 变为1，right 变为5。
   • 第二次循环：left 指向 'a'，right 指向 'a'。两者相等。left 变为2，right 变为4。
   • 第三次循环：left 指向 'c'，right 指向 'c'。两者相等。left 变为3，right 变为3。
   • 此时 left (3) 不再小于 right (3)，循环终止。中间的字符 'e' (索引3) 没有被任何比较涉及到，但这是正确的，因为中间字符无需配对，它自身即满足回文特性。如果字符串是回文串，那么所有外部配对的字符必然相等，中间字符的存在不影响判断结果。

因此，while (left < right) 条件能够正确处理奇数和偶数长度的字符串，且不会“遗漏”中间字符的判断，因为它本来就不需要被判断。

文心大模型

百度飞桨-文心大模型 ERNIE 3.0 文本理解与创作

56

查看详情

while (left <= right) 条件的适用场景

虽然 while (left < right) 对于回文串检测已经足够，但在某些情况下，你可能会考虑使用 while (left <= right)。这种条件意味着循环会一直执行，直到 left 指针越过 right 指针。对于奇数长度字符串，这意味着当 left 和 right 都指向中间字符时，循环会额外执行一次。

例如，对于“racecar”，当 left 和 right 都指向 'e' 时，left <= right 仍然为 true，循环会再次执行。此时 newStr[left] (即 'e') 会与 newStr[right] (即 'e') 进行比较，结果必然相等。之后 left 递增，right 递减，导致 left 变为4，right 变为2，left <= right 为 false，循环终止。

何时使用 while (left <= right)？

• 对中间元素有特定处理需求时：如果你的算法不仅仅是判断回文，还需要对字符串的每个字符（包括中间字符）进行某种操作，那么 left <= right 可以确保所有字符都被访问到。
• 语义清晰：有些人可能觉得 left <= right 更符合“遍历所有潜在配对”的直觉。

然而，对于标准的回文串检测，使用 while (left < right) 更为简洁和高效，因为它避免了对中间字符进行一次不必要的自我比较。

代码示例与解析

以下是使用双指针模式解决回文串问题的完整 JavaScript 代码：

/**
 * 检查给定字符串是否为回文串
 * @param {string} s 输入字符串
 * @returns {boolean} 如果是回文串则返回 true，否则返回 false
 */
var isPalindrome = function(s) {
    // 1. 预处理字符串：
    //    - 转换为小写，以忽略大小写差异。
    //    - 移除所有非字母数字字符（使用正则表达式 /[^0-9a-z]/g）。
    //      - `[0-9a-z]` 匹配数字和英文字母。
    //      - `^` 在字符集内部表示取反，即匹配不在字符集内的字符。
    //      - `g` 表示全局匹配，替换所有符合条件的字符。
    const newStr = s.toLowerCase().replace(/[^0-9a-z]/g, "");

    // 2. 初始化双指针：
    //    - left 指针从字符串开头开始。
    //    - right 指针从字符串末尾开始。
    let left = 0;
    let right = newStr.length - 1;

    // 3. 循环比较字符：
    //    - 循环条件 `left < right` 确保只要左右指针尚未相遇或交叉，就继续比较。
    //    - 对于奇数长度字符串，中间字符无需单独比较。
    while (left < right) {
        // 比较左右指针指向的字符。
        // 如果不相等，则字符串不是回文串，立即返回 false。
        if (newStr[left] !== newStr[right]) {
            return false;
        }

        // 如果相等，则移动指针继续向中间靠拢。
        left++;  // 左指针向右移动一位
        right--; // 右指针向左移动一位
    }

    // 4. 返回结果：
    //    - 如果循环完成（即所有比较的字符都相等），则字符串是回文串。
    return true;
};

// 示例测试
console.log("racecar:", isPalindrome('racecar'));                     // 输出: racecar: true
console.log("A man, a plan, a canal: Panama:", isPalindrome('A man, a plan, a canal: Panama')); // 输出: A man, a plan, a canal: Panama: true
console.log("Ceci n’est pas une palindrome:", isPalindrome('Ceci n’est pas une palindrome')); // 输出: Ceci n’est pas une palindrome: false
console.log(" ", isPalindrome(' '));                                 // 输出:  : true (空字符串或只含非字母数字字符的字符串处理后为空，视为回文)
console.log("ab_a", isPalindrome("ab_a"));                           // 输出: ab_a: true

注意事项与最佳实践

1. 字符串预处理：这是解决回文串问题的关键一步。忽略大小写和非字母数字字符能确保算法的通用性和健鲁性。正则表达式 /[^0-9a-z]/g 是一个非常实用的工具。
2. 指针初始化：left 指针应初始化为0，right 指针应初始化为 length - 1。
3. 循环条件的选择：
   • 对于标准回文串检测，while (left < right) 是最推荐的。它效率高，且语义清晰，避免了对中间单个字符的冗余比较。
   • 如果确实需要对所有字符（包括奇数长度字符串的中间字符）进行处理，可以考虑 while (left <= right)。
4. 时间复杂度：O(N)，其中 N 是处理后的字符串长度。因为每个字符最多被访问一次（当指针移动时）。预处理阶段也通常是线性的。
5. 空间复杂度：O(N)，用于存储预处理后的字符串。如果允许直接在原始字符串上操作（例如，通过跳过非字母数字字符），则空间复杂度可以优化到 O(1)，但这会使代码逻辑更复杂。在JavaScript中，由于字符串的不可变性，通常需要额外的空间来存储预处理后的字符串。

总结

双指针模式是解决回文串问题的一种优雅且高效的方法。通过从字符串两端向中间移动指针并进行比较，我们可以有效地判断字符串是否为回文。理解 while (left < right) 循环条件的精确作用，特别是其对奇数长度字符串的正确处理，是掌握此算法的关键。合理的字符串预处理和对时间、空间复杂度的考量，将帮助你编写出更健壮、性能更优的代码。

以上就是回文串检测：双指针算法详解与边界处理的详细内容，更多请关注php中文网其它相关文章！