Python frozenset

Some questions can be solved by using frozenset.

1178. Number of Valid Words for Each Puzzle

Number of Valid Words for Each Puzzle - LeetCode

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.

[Python] Find all Sub Puzzles - LeetCode Discuss

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

Detailed Explanation using Trie O(word_length + 100*puzzle_length) - LeetCode Discuss

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.