0680. Valid Palindrome II (Easy)

Question

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1

1
2

Input: "aba"
Output: True

Example 2

1
2
3

Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

Note:

1. The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

分析/解題

給定一個非空白的字串s，最多可以從當中刪除掉一個字元，
試判斷你能否讓這個字串變成一個回文。

回文(Palindrome)先前已經介紹過了 ，
就是符合「從尾到頭和從頭到尾看起來相同」即可，
所以它可以是像是abcba 的形式(中間有一個單獨的字元)，
或者是abba (成對兩兩相對)，這個概念在很多回文的題目都有用到，
讀者可以多加留意。

假設今天不能刪除任何字元的話，
問題就會直接變成檢查字串是否是回文，
那麼我們就可以直接設定兩個index i, j，
當中i從0開始遞增，j從s.length()-1(或len(s)-1)開始遞減 ，
依序對照對稱的位置檢查字元是否相等 即可。
(檢查到i, j交會都還兩兩對稱相等，則為回文)

好，那麼問題來了：
如果原先不是回文，需要刪掉一個字元才能變成回文呢？
該刪哪個？
有一句話說得好：
「解決不了問題，就解決產生問題的人」(大誤)，
既然我們只有一個可以刪的空間，
那麼就只能等到有無法對應到的狀況才處理。
舉例來說：
abcce ba -> a-a, b-b, 在c-e這個地方沒有對應到，
那麼有可能是c有問題，也有可能是e有問題，
所以我們可以分成刪掉c或刪掉e的狀況來檢查。
(因為實際上我們不會預先知道是誰有問題，也有可能都有問題)
也就是說，
當i, j沒辦法對應到時，我們可以選擇略過i 的位置上的字元，
或者略過j 的位置上的字元。(因為只是要檢查，所以不用真的作刪除)
略過i 的話，我們就要嘗試拿i+1來和j做對應 ；
略過j 的話，則是拿i和j-1做對應 。
剩下的狀況，就是按照前面一般檢查回文的流程依序檢查，
只要這兩條路其中一種 可以讓s變為回文，答案就會是true 。
那麼，如果又碰到沒對應到的呢？

那我們就只能說抱歉了XD~
我們已經用掉了一次刪除的機會，
後面再碰到對應不上的，當然就是不能成為回文囉！
所以這題看似會產生分支，其實只會產生一次而已，
因為我們只能刪一次而已，所以這題的時間複雜度並不高。

依此，我們寫成程式碼如下：

Java

Java的部分求方便起見，使用了toCharArray()，
我們將後續略過1個字元檢查的函式稱為isp(isPalindrome)，
當validPalindrome內的迴圈檢查到不符合的時候，
便呼叫isp來分支檢查；進入isp時，則只有所有剩下的字元兩兩對應，
才會回傳true，否則一定會回傳false。

Python

Python的部分，一樣不要忘記被用到的子函式要先宣告在前面，
其它和Java的解大同小異。

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(len(s))/O(1)，
由於最多分支就只有一次，
所以總體的複雜度還是跟字串長有關；
Java的部分因為偷懶使用toCharArray()，
所以空間複雜度也是O(len(s))，願意節省一點的話，
也可以用CharAt()來取得某個位置的字元。)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

感謝大家對這系列文章的支持！這邊跟大家自我工商一下：

筆者開設的系列同名線上課程：
「從Leetcode學演算法｜基礎篇」已經上線啦！ 在這堂課中，你將學會利用十種演算法/資料結構來優化解題過程，
並實際完整練習20題 精選考古題，
進而逐漸提升到不需提示也可以突破白板題，取得工作門票！
Medium優惠(最後一波早鳥優惠了，不確定調回原價是什麼時候)： ** https://hiskio.com/courses/319?promo_code=VE9Q5VE**