【LeetCode】916. Word Subsets 解題報告

撰寫於2022-08-01閱讀次數

916. Word Subsets / Medium

You are given two string arrays words1 and words2.

A string b is a subset of string a if every letter in b occurs in a including multiplicity.

For example, "wrr" is a subset of "warrior" but is not a subset of "world".
A string a from words1 is universal if for every string b in words2, b is a subset of a.

Return an array of all the universal strings in words1. You may return the answer in any order.

Example 1:

Input: words1 = [“amazon”,”apple”,”facebook”,”google”,”leetcode”], words2 = [“e”,”o”]
Output: [“facebook”,”google”,”leetcode”]

Example 2:

Input: words1 = [“amazon”,”apple”,”facebook”,”google”,”leetcode”], words2 = [“l”,”e”]
Output: [“apple”,”google”,”leetcode”]

Constraints:

  • 1 <= words1.length, words2.length <= 10^4
  • 1 <= words1[i].length, words2[i].length <= 10
  • words1[i] and words2[i] consist only of lowercase English letters.
  • All the strings of words1 are unique.

Solution: Reduce to Single Word in B

思路

這題看起來很複雜，一個一個暴力比對會超時，所以我們先把 words2 裡面的字串的字串都 reduce 成一個。
例如 “arr” + “row” 就可以被 reduce 成 “arrow”。我們用一個陣列作為 map 來儲存。
之後就是一個一個從 words1 中拿出字串來比對，如果通過比對就放入答案的陣列，最後回傳。

效能

Complexity

  • Time Complexity: O(A+B), where A and B is the information of word1 and words2.
  • Space Complexity: O(A.len + B.en)

LeetCode Result

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<string> wordSubsets(vector<string>& words1, vector<string>& words2) {
        vector<string> res;
        int i = 0;
        vector<int> count2(26, 0);
        for(auto& word: words2) {
            auto tmp = counter(word);
            for(int i = 0; i < 26; ++i) {
                count2[i] = max(count2[i], tmp[i]);
            } 
        }
        
        for(auto& word: words1) {
            auto tmp = counter(word);
            for(i = 0; i < 26; ++i) {
                if(tmp[i] < count2[i]) {
                    break;
                }
            }
            if(i == 26) res.emplace_back(word);
        }
        return res;
    }
    
    vector<int> counter(string word) {
        vector<int> res(26, 0);
        for(auto& c: word) {
            res[c-'a']++;
        }
        return res;
    }
};