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)。

思考

你能夠將上述代碼改造成迭代形式的嗎？