題目描述:給定一個字串 s,最多可以刪除一個字元,判斷能否讓字串成為回文。
解題思路:使用雙指針從字串兩端向中間掃描。當左右指針指向的字元相同時,同時向內收縮。若遇到不匹配的字元,有兩個選擇:跳過左指針指向的字元,或跳過右指針指向的字元。只要其中一種跳法讓剩餘子字串是回文,就回傳 true。若雙指針一路走到中間都未遇到不匹配,則原字串本身即為回文,直接回傳 true。核心貪心思想:遇到第一個不匹配時只能用掉「那一次刪除機會」,之後不能再刪。
時間複雜度:O(n) — 主迴圈最多掃描整個字串一次,遇到不匹配時呼叫兩次 isPalin,每次最多 O(n),整體仍為線性。
空間複雜度:O(1) — 只使用常數個指針變數,無額外資料結構。
1. Set left pointer l = 0, right pointer r = len(s) - 1.
2. While l < r:
a. If s[l] == s[r]: move both pointers inward (l++, r--).
b. Else (mismatch found):
- Check if s[l+1..r] is a palindrome (skip left char).
- Check if s[l..r-1] is a palindrome (skip right char).
- Return true if either check passes, false otherwise.
3. If the loop completes without mismatch, return true.方法一:暴力枚舉(Brute Force) — 嘗試刪除每個位置的字元,對每個結果做回文判斷,時間複雜度 O(n²),空間 O(n)。當 n 最大為 5×10⁵ 時會 TLE,僅適合理解題意。
方法二:雙指針 + 貪心(最優解) — 如本題解所示,O(n) 時間、O(1) 空間。遇到第一個不匹配就立刻分兩種跳法各驗一次,不需要回溯。