Re: [閒聊] 每日LeetCode

[pandix (麵包屌)]

76. Minimum Window Substring

給你兩個 string s and t  問你能讓 t 的每個字元都出現的 s 的最短 substring

t 會包含 duplicate characters

Example 1:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Example 2:
Input: s = "a", t = "a"
Output: "a"

Example 3:
Input: s = "a", t = "aa"
Output: ""


思路:

1.因為 substring 是連續的可以用左界右界去檢查 如果 t 不會重複就簡單了

維護一個 set 和 set(t), left right 都從 0 開始

如果目前子字串合法就推進 left  反之推進 right

推進 left 的意思: 拔掉 s[left], 檢查 s[left] 有沒有在 set(t) 裡 有就拔掉

推進 right 的意思: 加進 s[right], 檢查 s[right] 有沒有在 set(t) 裡 有就加

合不合法就是看目前 set 的長度有沒有跟 set(t) 的長度一樣


2.但是 t 會重複 所以改用 dict  概念還是差不多就是

這裡要再開一個 dict 去和 dict(t) 比較也是可以 只是 code 會變得很長

所以稍微改變一下 dict 的意思 不是字元目前出現的數量 而是還缺多少個

這樣就能算完 t 的數量之後把 tdict = Counter(t) 直接拿來用

另外檢查合不合法也多開一個變數去記 意思也是目前差多少個目標字元 tlen = len(t)

推進 left: tdict[s[left]] += 1 意思是拔掉 s[left] 後他的需求數量變多了

           tlen += (tdict[s[left]] > 0) 如果拔掉會讓他的需求超過 1 就加上去

這裡要多檢查是因為有些 s 的字元一開始不會出現在 tdict 中

所以要想辦法在更新 tlen 的時候忽略掉他們 而因為字元一定是先被 right 碰到

也就是先加入後移除 所以一開始不在 tdict 當中的字元 他的需求數量一定是 <= 0

這種字元我們在更新 tlen 時就不用理他了 不會影響合不合法

最後 怎麼檢查合不合法? 就是看 tlen 等不等於 0


Python code:

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        n, tdict, tlen = len(s), Counter(t), len(t)

        left, right = 0, 0
        res, reslen = "", float('inf')

        while r <= n:
            if tlen == 0:
                if r-l+1 < reslen:
                    res = s[l:r]
                    reslen = r-l+1

                tdict[s[l]] += 1
                tlen += (tdict[s[l]] > 0)
                l += 1

            else:
                if r == n:
                    break

                tdict[s[r]] -= 1
                tlen -= (tdict[s[r]] >= 0)
                r += 1

        return res


單迴圈版本 寫完覺得跟班長一樣醜

再參考一下別人的 iterate 右界 推進左界直到不合法

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        n, tdict, tlen = len(s), Counter(t), len(t)

        left, right = 0, 0
        res, reslen = "", float('inf')

        for right in range(n):
            tlen -= tdict[s[right]] > 0
            tdict[s[right]] -= 1

            while tlen == 0:
                if right-left < reslen:
                    res = s[left:right+1]
                    reslen = right-left

                tdict[s[left]] += 1
                tlen += tdict[s[left]] > 0
                left += 1

        return res

有稍微順眼一點了

--

沒人在乎

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.195.223 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1666424181.A.603.html
推 oin1104: 288
→ Rushia: 好難:(
推 NTHUlagka: 大師
推 abcd991276: 大ㄙ