前往
大廳
主題

LeetCode - 0916. Word Subsets 解題心得

Not In My Back Yard | 2023-07-06 12:00:07 | 巴幣 2 | 人氣 108

題目連結:


題目意譯:
你被給定兩個字串陣列 words1 和 words2。

如果一字串 b 中每個字母都出現於另一字串 a 之中(重複字母要分開算),則 b 為 a 的子集合。

例如,"wrr" 為 "warrior" 的一個子集合,但不是 "world" 的子集合。

如果 words1 中有一字串 a 滿足 words2 中的每一個字串 b 都是 a 的子集合,則我們將稱呼 a 為「普遍的」。

回傳一個裝有所有 words1 中的普遍字串之陣列。你可以按任意順序來回傳。

限制:
1 ≦ words1.length, words2.length ≦ 10 ^ 4
1 ≦ words1[i].length, words2[i].length ≦ 10
words1[i] 和 words2[i] 只由小寫英文字母組成。
words1 中的字串彼此相異。



範例測資:
範例 1:
輸入: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
輸出: ["facebook","google","leetcode"]

範例 2:
輸入: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["l","e"]
輸出: ["apple","google","leetcode"]


解題思維:
首先我們觀察一下普遍字串有什麼特性:
假設現在有一個普遍字串為 "aaabbbbbcd",而其普遍於 "ac" 、 "bb" 、 "bbbb" 、 "aa" 這些字串。

根據定義,"dbabacbab" 或是 "cbdbbaaab" 等排列組合也是普遍字串。因此我們可以看到重要的不是字母的順序,而是數量。

單看字母 'a' 的話,我們的普遍字串有 3 個 'a'。而其他字串("ac" 、 "bb" 等)依序為 1 、 0 、 0 、 2 個。所以可以看到單就 'a' 來說,要成為普遍字串必須至少滿足 2 個 'a' 的「需求」(因為 2 是其餘字串中數量最大值)。

而其他字母也是同理,即要成為普遍字串至少要有 4 個 'b' 以及 1 個 'c'。



因此我們可以先掃過 words2 中每個字串來統計每一種字母的最大「需求」。然後再掃過 words1 中每一個字串 words1[i],看看 words1[i] 的每一種字母出現次數是否滿足需求。如果有,則 words1[i] 即為一個普遍字串;反之則不是。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作