3.1　验证回文字符串Ⅱ

从数据结构上讲，字符串或许是最简单的回文类型了，我们就先从回文字符串讲起。

题目描述（第680题）

给定一个非空字符串s，要求最多删除一个字符，判断其是否能成为回文字符串。

示例1

输入："aba"

输出：True

示例2

输入："abca"

输出：True

解释：可以删除c字符。

注意：字符串只包含从a~z的小写字母，字符串的最大长度是50000。

思路

这是一道Facebook的面试题，在力扣（LeetCode）上标记的难度级别为简单，是一道热身题。

上文提到了回文，回文是正读反读结果都一样的句子，因此一种直接的思路是建立两个指针，分别指向头和尾，然后同步地“读”。如果发现不一致，那么说明不是回文，如果两个指针相遇了都没有发现不一致，就说明是一个回文字符串。

具体算法如下。

1．建立头/尾双指针l和r，分别指向字符串的第一个元素和最后一个元素。

2．比较两个指针对应的字符。

●　如果两个字符相同，则更新双指针，即l+=1，r-=1。

●　如果两个字符不同，则直接返回False。

3．重复步骤2。如果l和r交会，则表示该字符串是回文字符串，直接返回True即可。

代码如下所示。

基于此，我们继续考虑“最多删除一个字符，然后判断其能否成为回文字符串”。对上述回文字符串算法稍加改造，然后加上一些额外的逻辑来解决本题。我们仍然采用头/尾双指针的方法，并且更新指针的逻辑和上面也是一样的，不同之处如下。

1．如果头/尾指针对应的字符相同，那么没有必要删除任何字符。

2．如果头/尾指针对应的字符不同，那么必须删除一个字符才可能使之回文，并且由于只能删除一次，接下来只需要判断剩下的字符串是否能够构成回文即可。

具体算法如下。

1．建立头/尾双指针l和r，分别指向字符串的第一个元素和最后一个元素。

2．如果l和r没有交会，则比较两个指针对应的字符。

●　如果两个字符相同，则更新双指针，即l+=1，r-=1，重复执行步骤2。

●　如果两个字符不同，考虑删除左指针对应的字符或删除右指针对应的字符，并观察删除之后是否可以构成回文字符串。如果可以，则直接返回True；如果不可以，则直接返回False。

3．表示该字符串不需要删除字符就已经是回文字符串，直接返回True。

代码

复杂度分析

●　时间复杂度：虽然使用了一层循环，且循环内部调用了isPalindrome，但由于每次循环isPalindrome最多只会执行两次，因此总的时间复杂度仍然是O(n)，其中n为字符串的长度。

●　空间复杂度：O(1)。

思考

你能够将上述代码改造成迭代形式的吗？