[Leetcode 每日精選] 680. 驗證回文字元串 Ⅱ

題目難度: 簡單

原題連結

今天繼續做每日一題, 這道題雖然難度是簡單, 但好像通過率不是很高(不到 40%), 值得思考一下. 另外還可以進一步擴充, 比如最多可以删除 k 個字元時判斷能否成回文 (方案 3 給出了一些思路, 感興趣的同學可以自行嘗試)

題目描述

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

• 字元串隻包含從 a-z 的小寫字母。字元串的最大長度是 50000。

題目樣例

示例 1

輸入

“aba”

輸出

True

解釋

本身就是回文

示例 2

輸入

“abca”

輸出

True

解釋

可以删除 b 或者 c 字元

題目思考

1. 注意資料規模很大, 如果直接删除每個字元再驗證的話需要 O(N^2)時間, 肯定會逾時
2. 怎麼利用隻删除 1 個字元這個條件?
3. 如果把題目擴充成可以删除 k 個字元呢, 你能想到什麼做法嗎?

解決方案

方案 1

思路

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

複雜度

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

代碼

Python 3

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)
           

C++

class Solution {
public:
    bool validPalindrome(string s) {
        function<bool(int, int, bool)> check = [&](int b, int e, bool canDelete) {
            while (b < e && s[b] == s[e]) {
                ++b;
                --e;
            }

            if (b >= e) {
                return true;
            }

            if (!canDelete) {
                return false;
            }

            return check(b + 1, e, false) || check(b, e - 1, false);
        };

        return check(0, s.size() - 1, true);
    }
};
           

方案 2

思路

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

複雜度

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

代碼

Python 3

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
           

C++

class Solution {
public:
    bool validPalindrome(string s) {
        auto isPalindrome = [&](int b, int e) {
            for(; b < e; ++b, --e) {
                if (s[b] != s[e]) {
                    return false;
                }
            }
            return true;
        };

        int b = 0;
        int e = s.size() - 1;

        while (b < e && s[b] == s[e]) {
            ++b;
            --e;
        }

        if (b >= e) {
            return true;
        }

        return isPalindrome(b + 1, e) || isPalindrome(b, e - 1);
    }
};
           

方案 3

思路

• 現在思考擴充問題:

  最多可以删除 k 個字元時判斷能否成回文

• 當 k 比較小的時候(<10)
  • 此時我們還可以繼續利用方案 1, 可以把 flag 改成一個計數器, 初始化為 k, 每次删除一個字元後計數器減 1, 直到計數器為 0 就不能删除了.
  • 但是如果 k 比較大的時候這種方案就不可行了, 因為每次計數-1 時都要考慮左或者右指針移動的情況, 即有 2 種選擇, 總共會有 2^k 個選擇
• 當 k 比較大的時候
  • 這時候的瓶頸在 k 而不在 n, 那我們完全可以換一種思路.
  • 從原字元串删除某些字元, 其實等價于找原字元串的子序列
  • 那麼如果我們能找出原始字元串的最長回文子序列, 然後比較原始長度 n 和它的長度之差是否小于等于 k, 是的話則說明可以删除兩者長度差個字元使得生成的字元串子序列回文
  • 找最長回文子序列可以參考516. 最長回文子序列, 屬于經典的二維動态規劃問題, 大緻思路就是 dp[b,e]表示[b,e]區間内的最長回文子序列, 轉移方程根據 s[b]和 s[e]是否相等分兩種情況, 此處就不贅述了, 有興趣的同學可以自己嘗試寫下代碼~

複雜度

• 時間複雜度
  • 如果繼續利用方案 1 的思路, 每次對計數器 -1 時都要進行 2 次選擇, 總共就是 2^k 次選擇, 每次判斷回文要 O(N), 是以總的時間複雜度是 O(N*2^k)
  • 如果利用最長回文子序列的思路, 則二維動态規劃需要兩重循環, 總的時間複雜度是 O(N^2)
• 空間複雜度
  • 方案 1 思路仍然為 O(N), 遞歸的棧的消耗
  • 最長回文子序列的思路是 O(N^2), dp 數組的消耗

大家可以在下面這些地方找到我~😊

我的知乎專欄

我的 CSDN

我的簡書

我的 Leetcode

我的牛客網部落格

我的公衆号: 每日精選算法題, 歡迎大家掃碼關注~😊