Start by creating an empty trie root node. Prepare to insert bitmask representations of words with up to 7 unique letters.
💡 Building the trie is essential to efficiently represent all word letter subsets for quick lookup during puzzle queries.
Line:self.root = TrieNode()
💡 The trie root node is the starting point for all word insertions and puzzle traversals.
insert
Insert mask for word 'aaaa' into trie
Convert 'aaaa' to a bitmask representing letter 'a' only, then insert this mask into the trie by creating nodes for letter 'a'.
💡 Inserting word masks builds trie paths that represent unique letter sets of words, enabling fast subset checks later.
Line:for i in range(26):
bit = (mask >> i) & 1
if bit:
if i not in node.children:
node.children[i] = TrieNode()
node = node.children[i]
node.count += 1
💡 The trie now has a path for letter 'a' with count incremented at the leaf node.
insert
Insert mask for word 'asas' into trie
Convert 'asas' to bitmask for letters 'a' and 's', then insert nodes for 'a' and 's' in the trie, incrementing count at the leaf.
💡 Words with multiple letters create deeper trie branches representing their letter subsets.
Line:for i in range(26):
bit = (mask >> i) & 1
if bit:
if i not in node.children:
node.children[i] = TrieNode()
node = node.children[i]
node.count += 1
💡 The trie now has a branch for 'a' leading to a child node for 's', representing 'as' subset.
insert
Insert mask for word 'able' into trie
Convert 'able' to bitmask for letters 'a','b','l','e', insert nodes for these letters sequentially in trie, increment count at leaf.
💡 Inserting words with multiple distinct letters creates longer trie paths representing their letter combinations.
Line:for i in range(26):
bit = (mask >> i) & 1
if bit:
if i not in node.children:
node.children[i] = TrieNode()
node = node.children[i]
node.count += 1
💡 The trie now contains a path for 'a'->'b'->'e'->'l' representing 'able' letters.
traverse
Start DFS for puzzle 'aboveyz'
Convert puzzle letters to bitmask and identify first letter bit. Begin recursive DFS from trie root to count valid words including first letter 'a'.
💡 DFS explores trie paths restricted to puzzle letters, ensuring only valid word subsets are counted.
💡 DFS starts with no letters matched yet, ready to explore valid branches.
traverse
DFS explores child node for letter 'a' (bit 0)
Since 'a' is in puzzle and is the first letter, recurse into child node for 'a' with has_first=True.
💡 Including the puzzle's first letter in the path is mandatory for valid words.
Line:for i, child in node.children.items():
if (puzzle_mask & (1 << i)) != 0:
res += self.dfs(child, puzzle_mask, first_bit, has_first or (i == first_bit))
💡 The path now includes the required first letter, enabling counting of valid words below.
compare
DFS counts words ending at node for 'a'
At node for 'a', count words ending here since has_first is true. Add count to result.
💡 Words ending at this node are valid if the first letter is included in the path.
Line:res = node.count if has_first else 0
💡 Words like 'aaaa' end here and are counted for this puzzle.
traverse
DFS explores child node for letter 's' (bit 18) from 'a'
Check if 's' is in puzzle letters; since it is not in 'aboveyz', skip this branch (prune).
💡 Pruning avoids exploring branches with letters not in the puzzle, improving efficiency.
Line:if (puzzle_mask & (1 << i)) != 0:
res += self.dfs(child, puzzle_mask, first_bit, has_first or (i == first_bit))
💡 Pruning prevents unnecessary recursion down invalid paths.
traverse
DFS explores child node for letter 'b' (bit 1) from 'a'
Letter 'b' is in puzzle letters, recurse into child node for 'b' with has_first true.
💡 Continuing recursion along puzzle letters explores deeper word subsets.
Line:res += self.dfs(child, puzzle_mask, first_bit, has_first or (i == first_bit))
💡 The path now includes letters 'a' and 'b', still valid for puzzle.
traverse
DFS explores child node for letter 'e' (bit 4) from 'b'
Letter 'e' is in puzzle letters, recurse into child node for 'e' with has_first true.
💡 Recursion continues down valid letter paths to find word endings.
Line:res += self.dfs(child, puzzle_mask, first_bit, has_first or (i == first_bit))
💡 The path now includes letters 'a','b','e', matching part of 'able'.
traverse
DFS explores child node for letter 'l' (bit 11) from 'e'
Letter 'l' is in puzzle letters, recurse into child node for 'l' with has_first true.
💡 Reaching leaf nodes with counts indicates valid words found.
Line:res += self.dfs(child, puzzle_mask, first_bit, has_first or (i == first_bit))
💡 The path now represents full letter set of 'able'.
compare
Count words ending at node for 'l'
Add count of words ending at this node to result since has_first is true.
💡 This count contributes to the total valid words for the puzzle.
Line:res = node.count if has_first else 0
💡 Words like 'able' are counted here as valid for the puzzle.
backtracking
Backtrack and finish DFS for puzzle 'aboveyz'
Return accumulated count of valid words for puzzle 'aboveyz' after exploring all valid trie branches.
💡 Backtracking aggregates counts from all valid paths to produce the final answer for the puzzle.
Line:return res
💡 The final count for 'aboveyz' is 1, matching the expected output.
traverse
Start DFS for puzzle 'abslute'
Convert puzzle letters to bitmask and identify first letter bit. Begin DFS from trie root to count valid words including first letter 'a'.
💡 Each puzzle triggers a fresh DFS traversal constrained by its letters.
💡 DFS will explore trie branches matching puzzle letters to find valid words.
traverse
DFS explores child node for letter 'a' (bit 0) for 'abslute'
Recurse into child node for 'a' since it is in puzzle letters and is the first letter.
💡 Including the puzzle's first letter is mandatory for valid words.
Line:for i, child in node.children.items():
if (puzzle_mask & (1 << i)) != 0:
res += self.dfs(child, puzzle_mask, first_bit, has_first or (i == first_bit))
💡 The path now includes the required first letter.
traverse
DFS explores child node for letter 'b' (bit 1) from 'a' for 'abslute'
Recurse into child node for 'b' since it is in puzzle letters.
💡 Recursion explores valid letter branches to find word endings.
Line:res += self.dfs(child, puzzle_mask, first_bit, has_first or (i == first_bit))
💡 The path now includes letters 'a' and 'b'.
traverse
DFS explores child node for letter 'e' (bit 4) from 'b' for 'abslute'
Recurse into child node for 'e' since it is in puzzle letters.
💡 Continuing recursion to find valid word endings.
Line:res += self.dfs(child, puzzle_mask, first_bit, has_first or (i == first_bit))
💡 The path now includes letters 'a','b','e'.
traverse
DFS explores child node for letter 'l' (bit 11) from 'e' for 'abslute'
Recurse into child node for 'l' since it is in puzzle letters.
💡 Reaching leaf nodes indicates valid words found.
Line:res += self.dfs(child, puzzle_mask, first_bit, has_first or (i == first_bit))
💡 The path now represents full letter set of 'able'.
compare
Count words ending at node for 'l' for 'abslute'
Add count of words ending at this node to result since has_first is true.
💡 This count contributes to the total valid words for the puzzle.
Line:res = node.count if has_first else 0
💡 Words like 'able' are counted here as valid for the puzzle.
reconstruct
Final aggregation and output
After processing all puzzles, collect and return the list of counts of valid words for each puzzle.
💡 The final output shows how many words match each puzzle's constraints.
Line:return res
💡 The algorithm efficiently counts valid words using trie and bitmask pruning.
from typing import List
class TrieNode:
def __init__(self):
self.count = 0
self.children = {}
class Solution:
def __init__(self):
self.root = TrieNode() # STEP 1
def insert(self, mask):
node = self.root
for i in range(26): # STEP 2-4
bit = (mask >> i) & 1
if bit:
if i not in node.children:
node.children[i] = TrieNode()
node = node.children[i]
node.count += 1
def dfs(self, node, puzzle_mask, first_bit, has_first):
res = node.count if has_first else 0 # STEP 7,12,19
for i, child in node.children.items():
if (puzzle_mask & (1 << i)) != 0: # STEP 6,9,15,16,17,18
res += self.dfs(child, puzzle_mask, first_bit, has_first or (i == first_bit))
return res # STEP 13,20
def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
for word in words: # STEP 2-4
mask = 0
for ch in set(word):
mask |= 1 << (ord(ch) - ord('a'))
if bin(mask).count('1') <= 7:
self.insert(mask)
res = []
for puzzle in puzzles: # STEP 5,14
first_bit = ord(puzzle[0]) - ord('a')
puzzle_mask = 0
for ch in puzzle:
puzzle_mask |= 1 << (ord(ch) - ord('a'))
res.append(self.dfs(self.root, puzzle_mask, first_bit, False))
return res
if __name__ == "__main__":
words = ["aaaa","asas","able","ability","actt","actor","access"]
puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
sol = Solution()
print(sol.findNumOfValidWords(words, puzzles)) # STEP 20
📊
Number of Valid Words for Each Puzzle - Watch the Algorithm Execute, Step by Step
Watching the trie construction and recursive traversal step-by-step reveals how bitmasking and pruning efficiently solve a complex subset problem.
✓ Trie structure efficiently encodes all word letter subsets for fast lookup.
This insight is hard to see from code alone because the trie is implicit and built incrementally.
✓ Recursive DFS prunes branches not in puzzle letters, drastically reducing search space.
Visualizing pruning clarifies why the algorithm is efficient despite exponential subsets.
✓ Including the puzzle's first letter in the path is mandatory and tracked via has_first flag.
This subtle condition is critical and often overlooked when reading code without visualization.
Practice
(1/5)
1. You are given a set of sticks with various lengths. The goal is to determine if these sticks can be arranged to form a perfect square, using all sticks exactly once. Which algorithmic approach is most suitable to guarantee an optimal solution for this problem?
easy
A. Backtracking with bitmasking and memoization to explore all subsets efficiently while pruning invalid paths.
B. Greedy algorithm that always picks the longest stick first and tries to form sides sequentially.
C. Dynamic programming based on subset sums without pruning or memoization.
D. Simple brute force recursion that tries all possible assignments of sticks to sides without optimization.
Solution
Step 1: Understand problem constraints
The problem requires using all sticks exactly once to form four equal sides, which is a partitioning problem with strict constraints.
Step 2: Identify suitable algorithm
Greedy approaches fail because local choices don't guarantee global feasibility. Simple brute force is correct but inefficient. DP without pruning is too slow. Backtracking with bitmask and memoization efficiently explores subsets and prunes invalid paths, guaranteeing optimality.
Final Answer:
Option A -> Option A
Quick Check:
Bitmask + memoization prunes repeated states [OK]
Hint: Bitmask + memoization prunes repeated states [OK]
Common Mistakes:
Assuming greedy always works for partitioning
Confusing DP without pruning as efficient
Ignoring memoization benefits
2. The following code attempts to solve Combination Sum II but contains a subtle bug. Identify the line causing the bug.
medium
A. Line with 'if i > start and candidates[i] == candidates[i-1]: continue' for duplicate skipping
B. Line with 'if candidates[i] > target: break' for pruning
C. Line with 'backtrack(i + 1, path + [candidates[i]], target - candidates[i])' recursive call
D. Line with 'prev = candidates[i]' inside the loop
Solution
Step 1: Understand duplicate skipping logic
The code uses 'if i > start and candidates[i] == candidates[i-1]: continue' to skip duplicates correctly.
Step 2: Identify subtle bug
The 'prev' variable is assigned but never used, which is redundant and may confuse readers. The actual duplicate skipping is done by the index comparison, so 'prev' should be removed to avoid confusion.
Final Answer:
Option D -> Option D
Quick Check:
Redundant 'prev' variable assignment is a subtle bug causing confusion [OK]
Hint: Duplicate skipping must be consistent and correct at recursion level; remove unused variables [OK]
Common Mistakes:
Using prev variable incorrectly
Skipping duplicates globally instead of per recursion level
Not pruning when candidate > target
3. What is the time complexity of the optimal iterative approach for generating all unique subsets from an array of length n that may contain duplicates?
medium
A. O(n^2) because of nested loops over the array
B. O(2^n) since each element doubles the subsets
C. O(2^n * n) due to generating all subsets and copying them
D. O(n * 2^n) because sorting dominates the complexity
Solution
Step 1: Identify main operations affecting complexity
Sorting takes O(n log n), which is dominated by subset generation. The algorithm generates all subsets (2^n) and copies subsets of average length O(n).
Step 2: Calculate total time complexity
Generating all subsets is O(2^n), and copying each subset of length up to n leads to O(2^n * n) total time.
Final Answer:
Option C -> Option C
Quick Check:
Copying subsets causes the extra factor n, not just 2^n [OK]
Hint: Copying subsets adds factor n to 2^n subsets [OK]
Common Mistakes:
Ignoring subset copying cost and saying O(2^n)
Confusing sorting cost as dominant
Mistaking nested loops as O(n^2)
4. What is the time complexity of generating all subsets of an array of size n using the bit manipulation approach shown below?
medium
A. O(2^n * n) because for each of the 2^n masks, we check n bits to build the subset
B. O(2^n) because there are 2^n subsets and each subset is generated in constant time
C. O(n^2) because of nested loops over n elements
D. O(n * 2^n) because each of the 2^n subsets requires iterating over n elements
Solution
Step 1: Identify outer loop complexity
The outer loop runs 2^n times, once per subset mask.
Step 2: Identify inner loop complexity
For each mask, the inner loop iterates n times to check each bit.
Final Answer:
Option D -> Option D
Quick Check:
Total time is 2^n * n due to mask and bit checks [OK]
Hint: Each subset requires checking n bits -> O(n*2^n) [OK]
Common Mistakes:
Assuming subset generation is O(2^n) ignoring bit checks
Confusing n^2 with 2^n * n
5. Suppose the Matchsticks to Square problem is modified so that each matchstick can be used multiple times (unlimited reuse). Which of the following algorithmic changes correctly adapts the solution to this variant?
hard
A. Use backtracking without bitmask, allowing repeated selection of sticks, and prune when side length exceeded.
B. Keep the bitmask to track used sticks but allow multiple bits per stick to represent reuse counts.
C. Remove the bitmask and use a classic unbounded knapsack DP to check if four sides can be formed from unlimited sticks.
D. Sort sticks and greedily assign sticks to sides repeatedly until all sides are formed.
Solution
Step 1: Understand unlimited reuse impact
Unlimited reuse means the problem becomes an unbounded partition problem, not a subset partition.
Step 2: Identify suitable algorithm
Bitmask tracking used sticks is invalid since sticks can be reused infinitely. Backtracking without bitmask is inefficient. Greedy fails due to partition constraints. Unbounded knapsack DP correctly models unlimited usage.
