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