給定字串
s，判斷最多刪除一個字元後，是否能成為回文。
Example:
Input: s = “abca” Output: true（刪除 ‘b’ 或 ‘c’ 後為回文）
Intuition
TIP
核心思路：雙指針從兩端往中間比對，遇到不同時嘗試跳過左或右其中一個字元，檢查剩餘部分是否為回文。
- 與 LC 125 Valid Palindrome 類似，但多了一次「容錯」機會
- 當
s[left] != s[right]時，有兩種選擇：跳過左邊或跳過右邊 - 只要其中一種跳過後剩餘子字串是回文就成立
Approaches
1. Brute Force - Try Removing Each Char — O(n²) / O(n)
- Idea: 對每個位置
i，刪除s[i]後檢查剩餘字串是否回文 - Time:
O(n²)- n 個位置各檢查 O(n) - Space:
O(n)- 建立子字串
Brute Force Code
class Solution {
fun validPalindrome(s: String): Boolean {
for (i in s.indices) {
val t = s.removeRange(i, i + 1)
if (t == t.reversed()) return true
}
return s == s.reversed()
}
}⭐ 2. Two Pointers + Greedy Skip — O(n) / O(1)
- Idea: 左右指針比對，遇到不匹配時分別嘗試跳過左或右，檢查子區間是否回文
- Time:
O(n)- 主迴圈 + 子區間檢查合計最多遍歷一次 - Space:
O(1)- 只用指針
class Solution {
fun validPalindrome(s: String): Boolean {
var left = 0
var right = s.length - 1
while (left < right) {
if (s[left] != s[right]) {
return isPalindrome(s, left + 1, right) ||
isPalindrome(s, left, right - 1)
}
left++
right--
}
return true
}
private fun isPalindrome(s: String, l: Int, r: Int): Boolean {
var left = l
var right = r
while (left < right) {
if (s[left] != s[right]) return false
left++
right--
}
return true
}
}WARNING
遇到不匹配時必須同時嘗試兩種跳過方向，只嘗試一邊可能漏掉正確答案。例如 "cupucu" 需要跳右邊才正確。
🔑 Takeaways
- Pattern: 相向雙指針 + 容錯機制
- Key trick: 不匹配時分支嘗試兩種跳法，是 Two Pointers 搭配 Greedy 的常見組合