[L1] 双指针判断回文字符串

一句话结论

对撞指针从两端向中间逐字符比对，全部匹配则为回文，时间 O(n)、空间 O(1)。

体系讲解

什么是回文

回文（Palindrome）指正读和反读完全相同的字符串，如 "racecar"、"abba"。

反转比较法（不推荐）

将字符串反转后与原字符串比较——逻辑简单，但需要 O(n) 额外空间存储反转结果，且一旦发现不匹配也必须完成整个反转才能返回。

对撞指针法（推荐）

$left 从下标 0 出发，$right 从末尾出发，每次比较当前两端字符：

• 相等 → 双指针各向中间移动一步
• 不等 → 立即返回 false（提前终止，平均性能优于反转法）
• $left >= $right → 全部通过，返回 true

"racecar"
 ^     ^   r == r → 移动
  ^   ^    a == a → 移动
   ^ ^     c == c → 移动
    ^      left >= right → true

"race"
 ^  ^      r == e? 否 → false（提前退出）

变体：忽略非字母数字字符与大小写

题目常要求过滤标点/空格、忽略大小写（LeetCode 125）。处理方式：跳过非 ctype_alnum() 字符，比较时用 strtolower()。

考察意图

考查候选人对对撞指针的基础应用，以及在字符串处理中对边界（奇偶长度）和提前退出的掌握；同时考察能否区分"功能正确但空间低效的反转法"与"空间最优的双指针法"。

追问链

1. 奇数长度字符串（如 "aba"）时，中间那个字符需要比较吗？
   简答：不需要。当 $left === $right 时，指针指向同一个字符，与自身比较必然相等，没有比较意义；循环终止条件 $left < $right 自然跳过了这种情况。

2. strrev() 直接反转后用 === 比较，和双指针有什么实质区别？
   简答：结果一致，但 strrev() 会分配 O(n) 额外内存并完成整个反转；双指针无额外内存、一旦发现不匹配立即返回，平均性能更好（最坏情况两者均 O(n)）。工程中可用 strrev()，面试要求空间 O(1) 时必须用双指针。

3. 如何处理 Unicode 多字节字符（如中文）的回文判断？
   简答：$str[0] 按字节索引，中文字符为多字节，直接下标访问会截断字符。需先用 mb_str_split() 将字符串拆成字符数组，再对字符数组做对撞指针比较。

易错点

1. 终止条件写成 $left <= $right：当字符串长度为奇数时，$left === $right 会让中间字符与自身比较，虽然结果仍正确，但造成一次无意义比较；更重要的是，如果后续逻辑依赖 $left < $right 的语义（如返回中间下标），会出错。统一用严格小于。
2. 忽略空字符串和单字符的边界：空字符串 "" 和单字符 "a" 都是回文，循环不会执行，直接返回 true——需确认代码在这两种情况下能正确返回，而非崩溃或返回错误值。
3. 变体中跳过字符后忘记再次检查边界：在带过滤的变体里，每次移动指针后需重新确认 $left < $right 再访问字符，否则可能因越界读到 null 而产生误判。

代码示例

<?php

// ── 基础版：纯字符串回文判断 ──────────────────────────────────────
function isPalindrome(string $s): bool
{
    $left  = 0;
    $right = strlen($s) - 1;

    while ($left < $right) {
        if ($s[$left] !== $s[$right]) return false;
        $left++;
        $right--;
    }

    return true;
}

// ── 变体：忽略非字母数字、不区分大小写 ───────────────────────────
function isPalindromeAlphanumeric(string $s): bool
{
    $chars = mb_str_split(strtolower($s));
    $left  = 0;
    $right = count($chars) - 1;

    while ($left < $right) {
        while ($left < $right && !ctype_alnum($chars[$left]))  $left++;
        while ($left < $right && !ctype_alnum($chars[$right])) $right--;
        if ($left < $right && $chars[$left] !== $chars[$right]) return false;
        $left++;
        $right--;
    }

    return true;
}

// 演示
var_dump(isPalindrome("racecar"));              // true
var_dump(isPalindrome("race"));                 // false
var_dump(isPalindromeAlphanumeric("A man, a plan, a canal: Panama")); // true