Leetcode 劍指 Offer II 019. 最多删除一個字元得到回文

題目難度: 簡單

原題連結[1]

今天繼續更新 Leetcode 的劍指 Offer（專項突擊版）系列, 大家在公衆号 算法精選 裡回複 劍指offer2 就能看到該系列目前連載的所有文章了, 記得關注哦~

題目描述

給定一個非空字元串 s，請判斷如果 最多 從字元串中删除一個字元能否得到一個回文字元串。

示例 1:

• 輸入: s = "aba"
• 輸出: true

示例 2:

• 輸入: s = "abca"
• 輸出: true
• 解釋: 可以删除 "c" 字元 或者 "b" 字元

示例 3:

• 輸入: s = "abc"
• 輸出: false

提示:

• 1 <= s.length <= 10^5
• s 由小寫英文字母組成

題目思考

1. 注意資料規模很大, 如果直接删除每個字元再驗證的話需要 O(N^2)時間, 肯定會逾時
2. 怎麼利用隻删除 1 個字元這個條件?

解決方案

方案 1

思路

• 回顧雙指針判斷字元串是否回文的過程, 此題加入了可以删除一個字元的可選項
• 是以可以遞歸處理, 在原來的基礎上加入一個 flag, 判斷目前是否還能删除
• 如果遇到不相等的字元時, 可以左邊指針往右移動一位, 或者右邊向左移動一位, 然後把 flag 置為 false 即可, 再遇到不相等的就說明不能變成回文了
• 遞歸傳入左邊界和右邊界表示雙指針, 注意遞歸出口
• 該方案優點是代碼非常簡潔, 思路也比較直覺, 缺點是需要額外的空間消耗

複雜度

• 時間複雜度 O(N): 遇到不相等的字元時, 需要再判斷兩次, 是以總時間是 O(2N) = O(N)
• 空間複雜度 O(N): 遞歸的棧的消耗

代碼

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def check(b, e, canDelete):
            if b >= e:
                return True
            if s[b] == s[e]:
                return check(b + 1, e - 1, canDelete)
            elif canDelete:
                # 還有一次删除機會, 左指針右移或者右指針左移, 同時更新flag保證之後的判斷不能再删除字元了
                return check(b + 1, e, False) or check(b, e - 1, False)
            else:
                # 遇到不相等的字元且不能再删除了, 直接傳回false
                return False

        return check(0, len(s) - 1, True)
           

方案 2

思路

• 回顧方案 1, 我們是把疊代做法的雙指針改成了遞歸版本, 那可不可以繼續疊代搞定呢? 這樣就不需要遞歸的棧的空間消耗了.
• 答案也是肯定的, 我們可以把在不能删除字元前提下的判斷回文的雙指針算法給提取出來
• 然後從兩邊開始往中間周遊, 遇到不相等的字元時就先後将兩邊的指針各往中間移動一位, 對剩下的兩個子字元串調用那個算法, 如果有一邊是回文, 則說明符合要求
• 該方案優點是空間複雜度更小, 但缺點是代碼沒有方案 1 簡潔

複雜度

• 時間複雜度 O(N): 遇到不相等的字元時, 需要再判斷兩次, 是以總時間是 O(2N) = O(N)
• 空間複雜度 O(1): 隻使用了幾個常數空間的變量

代碼

class Solution:
    def validPalindrome(self, s: str) -> bool:
        b = 0
        e = len(s) - 1

        def isPalindrome(b, e):
            while b < e:
                if s[b] == s[e]:
                    b += 1
                    e -= 1
                else:
                    return False
            return True

        while b < e:
            if s[b] == s[e]:
                b += 1
                e -= 1
            else:
                return isPalindrome(b + 1, e) or isPalindrome(b, e - 1)
        return True
           

參考資料

[1]

原題連結: https://leetcode.cn/problems/RQku0D