最多删除一个字符判断回文串，为什么要在第一次不匹配处分叉？

简化版

最多删除一个字符判断回文，可以用相向双指针。

左右字符相等就继续向中间走；第一次不相等时，只可能删除左字符或右字符。

只要 s[left+1..right] 或 s[left..right-1] 有一个是回文，就返回 true。

详细版

普通回文判断是左右指针逐步比较。

本题允许删除一个字符，所以当 s[left] !== s[right] 时，不能直接返回 false。由于之前的外层字符都已经匹配，破坏回文的只可能是当前左端或右端其中一个。

因此做两次辅助检查：

isPalindrome(left + 1, right) || isPalindrome(left, right - 1)

如果任意一个成立，说明删除一个字符后能成为回文。

整个过程最多额外扫描一次字符串，所以时间复杂度 O(n)，空间复杂度 O(1)。

完整版教学

一、为什么只需要处理第一次不匹配

相向双指针从两端往中间比较。只要前面字符都匹配，它们就不会再影响答案。第一次出现 s[left] !== s[right] 时，如果还能通过删除一个字符变成回文，那么被删除的字符一定是 left 或 right 之一。删除中间其他字符无法修复当前这对不相等的边界。

记忆钩子：回文的矛盾出现在两端，删除机会也只能先给这两端。

二、为什么要分两种情况

当左右不匹配时，我们不知道问题出在左边还是右边。比如 "abca"，左右 a 匹配后，b 和 c 不匹配；删除 b 得到 "aca"，删除 c 得到 "aba"，两者都可行。再比如 "deeee"，第一次不匹配是 d 和 e，只能删除 d。

字符串	不匹配位置	删除左端	删除右端
`abca`	`b` vs `c`	可行	可行
`deeee`	`d` vs `e`	可行	不可行
`abc`	`a` vs `c`	不可行	不可行

所以必须检查两条分支。

三、辅助函数怎么写

辅助函数就是普通回文判断：

function check(s, left, right) {
  while (left < right) {
    if (s[left] !== s[right]) return false
    left++
    right--
  }
  return true
}

主函数只在第一次不匹配时调用它。这样不会出现指数级分叉，因为删除机会只有一次。

四、完整代码

实现如下：

function validPalindrome(s) {
  let left = 0
  let right = s.length - 1
  while (left < right) {
    if (s[left] === s[right]) {
      left++
      right--
    } else {
      return check(s, left + 1, right) || check(s, left, right - 1)
    }
  }
  return true
}

这里的 check 可以定义在函数外，也可以作为内部函数。核心是第一次不匹配后立即返回两个分支的结果。

五、为什么复杂度仍然是 O(n)

主循环最多扫描一半字符串。第一次不匹配后，两个辅助检查各自最多扫描剩余区间的一部分。虽然看起来有两个分支，但它们不是递归继续分叉，总扫描量仍然是常数倍的 n。

主扫描 O(n)
删除左检查 O(n)
删除右检查 O(n)
总计 O(n)

空间上只用了指针，是 O(1)。

六、常见误区与追问

误区：第一次不匹配就返回 false。 题目允许删除一个字符，必须给一次修复机会。
误区：只尝试删除左边。 有些字符串只能删除右边才能成回文。
误区：用递归暴力删除每个字符。 删除机会只有一次，在首次不匹配处分叉就足够。
追问：如果允许删除 K 个字符怎么办？ 这会变成区间动态规划或带记忆化搜索问题，不能简单套本题模板。
追问：为什么不删除中间字符？ 当前左右端已经不等，删除中间字符不能让这两个字符相等。

这些问题考察的是“第一次矛盾决定删除候选”的贪心逻辑。

七、加强记忆

这题记成“普通回文一路走，第一次冲突分左右”。左右相等就收缩；第一次不相等时，删除机会只能用于左端或右端，于是检查两个剩余区间是否回文。因为只分叉一次，所以复杂度仍然线性。千万不要把它写成删除任意字符的暴力搜索。

简化版

详细版