680. Valid Palindrome II

Easy

Description

給定字串 s，判斷最多刪除一個字元後，是否能成為回文。

Example:

Input: s = “abca” Output: true（刪除 ‘b’ 或 ‘c’ 後為回文）

Intuition#

核心思路：雙指針從兩端往中間比對，遇到不同時嘗試跳過左或右其中一個字元，檢查剩餘部分是否為回文。

與 LC 125 Valid Palindrome 類似，但多了一次「容錯」機會
當 s[left] != s[right] 時，有兩種選擇：跳過左邊或跳過右邊
只要其中一種跳過後剩餘子字串是回文就成立

Approaches#

1: Brute Force - 嘗試刪除每個字元#

概念: 對每個位置 i，刪除 s[i] 後檢查剩餘字串是否回文
時間複雜度: O(n²) - n 個位置各檢查 O(n)
空間複雜度: O(n) - 建立子字串

Brute Force 程式碼

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 + 貪心跳過#

概念: 左右指針比對，遇到不匹配時分別嘗試跳過左或右，檢查子區間是否回文
時間複雜度: O(n) - 主迴圈 + 子區間檢查合計最多遍歷一次
空間複雜度: 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
    }
}

遇到不匹配時必須同時嘗試兩種跳過方向，只嘗試一邊可能漏掉正確答案。例如 "cupucu" 需要跳右邊才正確。

🔑 Takeaways#

Pattern: 相向雙指針 + 容錯機制
關鍵技巧: 不匹配時分支嘗試兩種跳法，是 Two Pointers 搭配 Greedy 的常見組合