Python frozenset

Some questions can be solved by using frozenset.

1178. Number of Valid Words for Each Puzzle

The naive approach will get TLE

`9 / 10 test cases passed.Status:`

Time Limit Exceeded

`class Solution:    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:        words = [tuple(sorted(set(w))) for w in words]        cnt = collections.Counter(words)        def get_num_valid_words(p, p0):            if not words:return 0            count = 0            for word in cnt:                if p0 in word and set(word).issubset(p):                    count += cnt[word]            return count                              return [get_num_valid_words(set(p), p[0]) for p in puzzles]`

Based on lee215’s post, we can use frozenset and consider all possible combinations for each puzzle to solve the problem.

https://leetcode.com/problems/number-of-valid-words-for-each-puzzle/discuss/371864/Python-Find-all-Sub-Puzzles

Part I

1. For each word `w` in `words`, calculate the set of word's letters.
2. count the number of different sets, save to the `counter`.

Part II

1. For each puzzle `p` in `puzzles`, calculate all subset of puzzle `p`.
The subset has to include the puzzle's first letter.
2. For each set of sub-puzzle, find its occurrence from the counter of the part.
3. Sum up the occurrences of all sub-puzzles, push it to the result list `res`

Complexity

Part I Time `O(W)`, space `O(W)`
Part II Time `O(2^6 * P)` = `O(64P)`, space `O(1)`

`class Solution:    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:        count = collections.Counter(frozenset(w) for w in words)        res = []        for p in puzzles:            cur = 0            for k in range(len(p)):                for c in itertools.combinations(p[1:], k):                    cur += count[frozenset(tuple(p[0]) + c)]            res.append(cur)        return res`

Runtime of above code

`Runtime: 1332 ms, faster than 9.02% of Python3 online submissions for Number of Valid Words for Each Puzzle.Memory Usage: 82.9 MB, less than 100.00% of Python3 online submissions for Number of Valid Words for Each Puzzle.`

We can also use trie to solve this problem as shown here

`const int ALPHABET_SIZE = 26;/* The structure of a trie node */struct TrieNode{    struct TrieNode* children[ALPHABET_SIZE];    int count = 0;};/* Creates a new trie node and returns the pointer */struct TrieNode* getNode(){    struct TrieNode* newNode = new TrieNode;for(int i = 0; i < ALPHABET_SIZE; i++)        newNode->children[i] = nullptr;        newNode->count = 0;return newNode;}/* Inserts the given string to the collection */void insert(struct TrieNode* root, string str){    struct TrieNode* pCrawl = root;for(int i = 0; i < str.length(); i++)    {        int index = str[i]-'a';if(!pCrawl->children[index])            pCrawl->children[index] = getNode();                pCrawl = pCrawl->children[index];    }pCrawl->count++;}/* Returns the count of strings which are valid */int search(struct TrieNode* root, string str, bool firstSeen, char firstLetter){    if(!root)        return 0;        int count = 0;        if(firstSeen)        count += root->count;        for(int i = 0; i < str.length(); i++)    {        int index = str[i] - 'a';                if(str[i] == firstLetter)            count += search(root->children[index], str, true, firstLetter);        else            count += search(root->children[index], str, firstSeen, firstLetter);    }return count;}class Solution{public:    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles);};vector<int> Solution :: findNumOfValidWords(vector<string>& words, vector<string>& puzzles){    struct TrieNode* root = getNode();        for(auto str : words)    {        set<char> temp;        temp.insert(str.begin(), str.end());                string sorted = "";        for(auto ele : temp)            sorted += ele;                insert(root, sorted);    }        vector<int> count;    for(auto puzzle : puzzles)    {        char firstLetter = puzzle[0];        sort(puzzle.begin(), puzzle.end());        count.push_back(search(root, puzzle, false, firstLetter));    }        return count;    }`

Runtime of above c++ code

`Runtime: 1368 ms, faster than 5.29% of C++ online submissions for Number of Valid Words for Each Puzzle.Memory Usage: 115 MB, less than 100.00% of C++ online submissions for Number of Valid Words for Each Puzzle.`

Python version

`class Solution:    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:        trie = {}        def addTrie(word):            cur = trie            for char in sorted(set(word)):                if char not in cur:                    cur[char] = {}                cur = cur[char]            if "total" not in cur:                cur["total"] = 0            cur["total"] += 1            def search(cur,puzzle,start,firstLetter, foundFirstLetter):            if not cur:                return 0            count = 0            if foundFirstLetter:                count += cur["total"] if "total" in cur else 0            for i in range(start,len(puzzle)):                if puzzle[i] not in cur:                    continue                if firstLetter == puzzle[i]:                    count += search(cur[puzzle[i]],puzzle,i+1,firstLetter,True)                else:                    count += search(cur[puzzle[i]],puzzle,i+1,firstLetter,foundFirstLetter)            return count            for word in words:            addTrie(word)            res = []            for puzzle in puzzles:            res.append(search(trie,sorted(puzzle),0,puzzle[0],False))        return res`

runtime

`Runtime: 1448 ms, faster than 5.74% of Python3 online submissions for Number of Valid Words for Each Puzzle.Memory Usage: 50.4 MB, less than 100.00% of Python3 online submissions for Number of Valid Words for Each Puzzle.`

Data Scientist/MLE/SWE @takemobi

More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi