string - 正确性的回文有效性证明

Question

Leetcode 描述

给定一个长度为的字符串n，您必须确定该字符串是否为回文，但您最多可以删除一个字符。

例如：“aba”是回文。
"abca" 也是有效的，因为我们可以删除 "b" 或 "c" 以获得回文。

我见过许多采用以下方法的解决方案。

用两个指针left分别right初始化为字符串的开始和结束字符，只要和所指向的两个字符相等，就保持同步递增和left递减。rightleftright

当我们第一次遇到 and 所指向的字符之间的不匹配时left，right并说这些是专门的索引iand j，我们只是检查string[i..j-1]or是否string[i+1..j]是回文。

我清楚地知道为什么会这样，但让我困扰的一件事是当我们第一次看到不匹配时我们采取的方法的方向。

假设我们不关心时间效率，只关注正确性，我看不出是什么阻止我们尝试删除一个字符，string[0..i-1]或者string[j+1..n-1]尝试查看整个结果字符串是否会变成回文？更具体地说，如果我们采用第一种方法并
看到两者都不是回文，那么是什么阻止我们回溯到我描述的第二种方法，看看是否删除一个字符或会产生一个回文？string[i..j-1]string[i+1..j]string[0..i-1]string[j+1..n-1]

我们能否在数学上证明为什么这种方法无用或根本不正确？

标签： stringpalindromeinvariantsloop-invariantproof-of-correctness