Leetcode 劍指 Offer II 017. 含有所有字元的最短字元串

題目難度: 困難

原題連結[1]

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

題目描述

給定兩個字元串 s 和 t 。傳回 s 中包含 t 的所有字元的最短子字元串。如果 s 中不存在符合條件的子字元串，則傳回空字元串 "" 。

如果 s 中存在多個符合條件的子字元串，傳回任意一個。

注意： 對于 t 中重複字元，我們尋找的子字元串中該字元數量必須不少于 t 中該字元數量。

示例 1：

• 輸入：s = "ADOBECODEBANC", t = "ABC"
• 輸出："BANC"
• 解釋：最短子字元串 "BANC" 包含了字元串 t 的所有字元 'A'、'B'、'C'

示例 2：

• 輸入：s = "a", t = "a"
• 輸出："a"

示例 3：

• 輸入：s = "a", t = "aa"
• 輸出：""
• 解釋：t 中兩個字元 'a' 均應包含在 s 的子串中，是以沒有符合條件的子字元串，傳回空字元串。

提示：

• 1 <= s.length, t.length <= 10^5
• s 和 t 由英文字母組成
• 進階：你能設計一個在 o(n) 時間内解決此問題的算法嗎？

題目思考

1. 如何在 o(n) 時間内解決此問題?

解決方案

思路

• 分析題目, 不難發現這道題和之前的題目劍指 Offer II 014. 字元串中的變位詞很類似, 隻不過這裡的子串字元數不是嚴格相等, 而是隻需要包含目标字元串的所有字元即可
• 是以我們可以舉一反三, 利用相同的滑動視窗思路, 隻需要稍微改變一下判斷條件和輸出, 具體做法如下:
• 首先我們可以先比較 s 和 t 的長度, 如果 s 更短, 則一定不可能包含 t 的全部字元, 直接傳回空字元串即可
• 然後建立兩個計數字典 cntt (初始化為 t 的字元計數)和 cnts (初始化為空)
• 同時維護一個尚未比對的字元個數 unmatch, 用于加速判斷視窗的有效性, 且其值初始化為 t 的長度, 因為還沒開始周遊 s
• 接下來開始周遊 s 的滑動視窗右邊界, 并将 cnts 中對應字元的計數加 1, 然後更新 unmatch: 如果加 1 之後的 cnts 計數小于等于 cntt 計數, 則說明找到一個有效包含字元, unmatch 減 1
• 如果目前 unmatch 變成了 0, 則說明目前視窗包含了 t 的所有字元, 需要開始移除左邊界, 因為題目要求最短子串
• 我們需要将 cnts 中目前左邊界對應字元的計數減 1, 然後左邊界右移, 并更新 unmatch: 如果減 1 之後的計數 cnts 計數小于 cntt 計數, 說明移除後 t 又多了一個未比對的該字元, unmatch 要加 1
• 當 unmatch 大于 0 時, 則說明前一個左邊界到目前右邊界對應的視窗是以目前右邊界作為終點的最短子串, 将其與最終結果比較, 并将最終結果更新為兩者中的較小值
• 下面代碼有詳細的注釋, 友善大家了解

複雜度

• 時間複雜度 O(N): 假設 M 是 t 的長度, N 是 s 的長度, 隻有 N>=M 時才需要周遊 s 的 N 個字元
• 空間複雜度 O(N): 最多存儲 N 個元素

代碼

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # 滑窗+雙計數字典+unmatch變量
        if len(s) < len(t):
            # s更短, 一定沒有滿足條件的子串
            return ""
        # 初始化t計數字典
        cntt = collections.Counter(t)
        # 初始化s計數字典為空, 因為尚未添加s的字元
        cnts = collections.Counter()
        # 初始化未比對數目是t的長度
        unmatch = len(t)
        l = 0
        res = ""
        for r, c in enumerate(s):
            # 周遊滑動視窗右邊界
            cnts[c] += 1
            if cnts[c] <= cntt[c]:
                # 新增一個有效包含字元
                unmatch -= 1
            if unmatch == 0:
                # 目前視窗包含t的全部字元, 開始移動左邊界
                while unmatch == 0:
                    pc = s[l]
                    cnts[pc] -= 1
                    if cnts[pc] < cntt[pc]:
                        # 減少一個有效包含字元
                        unmatch += 1
                    l += 1
                # 此時s[l-1:r+1]就是以r為終點的最短有效子串
                if res == "" or len(s[l - 1 : r + 1]) < len(res):
                    res = s[l - 1 : r + 1]
        return res
           

參考資料

[1]

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