🧠
Bitmask + Trie Optimization (Advanced)
💡 This approach uses a trie data structure to store word bitmasks and prune search space when enumerating puzzle subsets, further optimizing performance.
Intuition
Build a trie where each node represents a letter bit. For each puzzle, traverse the trie only along paths that correspond to puzzle letters and include the first letter, counting valid words efficiently.
Algorithm
- Build a trie where each path corresponds to a unique combination of letters from words.
- Each trie node stores the count of words ending at that node.
- For each puzzle, recursively traverse the trie, only following branches corresponding to puzzle letters.
- Ensure the first letter of the puzzle is included in the path before counting words.
💡 Trie traversal prunes invalid subsets early, avoiding enumeration of all subsets explicitly.
from typing import List
class TrieNode:
def __init__(self):
self.count = 0
self.children = {}
class Solution:
def __init__(self):
self.root = TrieNode()
def insert(self, mask):
node = self.root
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
def dfs(self, node, puzzle_mask, first_bit, has_first):
res = node.count if has_first else 0
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))
return res
def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
for word in words:
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:
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
# Driver code
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))
Line Notes
class TrieNode:Define trie node with count and children
def insert(self, mask):Insert word bitmask into trie by bits set
def dfs(self, node, puzzle_mask, first_bit, has_first):Recursively traverse trie pruning by puzzle letters
res = node.count if has_first else 0Count words only if first letter included in path
import java.util.*;
class TrieNode {
int count = 0;
Map<Integer, TrieNode> children = new HashMap<>();
}
public class Solution {
TrieNode root = new TrieNode();
void insert(int mask) {
TrieNode node = root;
for (int i = 0; i < 26; i++) {
if (((mask >> i) & 1) == 1) {
node.children.putIfAbsent(i, new TrieNode());
node = node.children.get(i);
}
}
node.count++;
}
int dfs(TrieNode node, int puzzleMask, int firstBit, boolean hasFirst) {
int res = hasFirst ? node.count : 0;
for (Map.Entry<Integer, TrieNode> entry : node.children.entrySet()) {
int i = entry.getKey();
TrieNode child = entry.getValue();
if ((puzzleMask & (1 << i)) != 0) {
res += dfs(child, puzzleMask, firstBit, hasFirst || i == firstBit);
}
}
return res;
}
public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
for (String word : words) {
int mask = 0;
for (char c : word.toCharArray()) {
mask |= 1 << (c - 'a');
}
if (Integer.bitCount(mask) <= 7) insert(mask);
}
List<Integer> res = new ArrayList<>();
for (String puzzle : puzzles) {
int firstBit = puzzle.charAt(0) - 'a';
int puzzleMask = 0;
for (char c : puzzle.toCharArray()) puzzleMask |= 1 << (c - 'a');
res.add(dfs(root, puzzleMask, firstBit, false));
}
return res;
}
public static void main(String[] args) {
String[] words = {"aaaa","asas","able","ability","actt","actor","access"};
String[] puzzles = {"aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"};
Solution sol = new Solution();
System.out.println(sol.findNumOfValidWords(words, puzzles));
}
}
Line Notes
class TrieNode {Trie node with count and children map
void insert(int mask) {Insert word bitmask into trie by bits set
int dfs(TrieNode node, int puzzleMask, int firstBit, boolean hasFirst) {DFS trie pruning by puzzle letters
int res = hasFirst ? node.count : 0;Count words only if first letter included
#include <bits/stdc++.h>
using namespace std;
struct TrieNode {
int count = 0;
unordered_map<int, TrieNode*> children;
};
class Solution {
TrieNode* root = new TrieNode();
void insert(int mask) {
TrieNode* node = root;
for (int i = 0; i < 26; i++) {
if ((mask >> i) & 1) {
if (!node->children.count(i)) node->children[i] = new TrieNode();
node = node->children[i];
}
}
node->count++;
}
int dfs(TrieNode* node, int puzzleMask, int firstBit, bool hasFirst) {
int res = hasFirst ? node->count : 0;
for (auto& [i, child] : node->children) {
if ((puzzleMask & (1 << i)) != 0) {
res += dfs(child, puzzleMask, firstBit, hasFirst || i == firstBit);
}
}
return res;
}
public:
vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
for (auto& word : words) {
int mask = 0;
unordered_set<char> unique_chars(word.begin(), word.end());
for (char c : unique_chars) mask |= 1 << (c - 'a');
if (__builtin_popcount(mask) <= 7) insert(mask);
}
vector<int> res;
for (auto& puzzle : puzzles) {
int firstBit = puzzle[0] - 'a';
int puzzleMask = 0;
for (char c : puzzle) puzzleMask |= 1 << (c - 'a');
res.push_back(dfs(root, puzzleMask, firstBit, false));
}
return res;
}
};
int main() {
vector<string> words = {"aaaa","asas","able","ability","actt","actor","access"};
vector<string> puzzles = {"aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"};
Solution sol;
vector<int> res = sol.findNumOfValidWords(words, puzzles);
for (int x : res) cout << x << " ";
cout << endl;
return 0;
}
Line Notes
struct TrieNode {Trie node with count and children map
void insert(int mask) {Insert word bitmask into trie by bits set
int dfs(TrieNode* node, int puzzleMask, int firstBit, bool hasFirst) {DFS trie pruning by puzzle letters
int res = hasFirst ? node->count : 0;Count words only if first letter included
class TrieNode {
constructor() {
this.count = 0;
this.children = new Map();
}
}
class Solution {
constructor() {
this.root = new TrieNode();
}
insert(mask) {
let node = this.root;
for (let i = 0; i < 26; i++) {
if ((mask >> i) & 1) {
if (!node.children.has(i)) node.children.set(i, new TrieNode());
node = node.children.get(i);
}
}
node.count++;
}
dfs(node, puzzleMask, firstBit, hasFirst) {
let res = hasFirst ? node.count : 0;
for (let [i, child] of node.children.entries()) {
if ((puzzleMask & (1 << i)) !== 0) {
res += this.dfs(child, puzzleMask, firstBit, hasFirst || i === firstBit);
}
}
return res;
}
findNumOfValidWords(words, puzzles) {
for (const word of words) {
let mask = 0;
const unique = new Set(word);
for (const ch of unique) {
mask |= 1 << (ch.charCodeAt(0) - 97);
}
if (this.countBits(mask) <= 7) this.insert(mask);
}
const res = [];
for (const puzzle of puzzles) {
const firstBit = puzzle.charCodeAt(0) - 97;
let puzzleMask = 0;
for (const ch of puzzle) {
puzzleMask |= 1 << (ch.charCodeAt(0) - 97);
}
res.push(this.dfs(this.root, puzzleMask, firstBit, false));
}
return res;
}
countBits(x) {
let count = 0;
while (x) {
count += x & 1;
x >>= 1;
}
return count;
}
}
// Driver code
const words = ["aaaa","asas","able","ability","actt","actor","access"];
const puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"];
const sol = new Solution();
console.log(sol.findNumOfValidWords(words, puzzles));
Line Notes
class TrieNode {Trie node with count and children map
insert(mask) {Insert word bitmask into trie by bits set
dfs(node, puzzleMask, firstBit, hasFirst) {DFS trie pruning by puzzle letters
let res = hasFirst ? node.count : 0;Count words only if first letter included
TimeO(W * L + P * M) where W = number of words, L = average word length, P = number of puzzles, M = trie traversal nodes per puzzle
SpaceO(W * L) for trie storage
Trie pruning reduces subset enumeration overhead by exploring only valid letter paths per puzzle.
💡 This approach is more complex but can be faster in practice when many words share letter subsets.
Interview Verdict: Accepted (Advanced)
This approach is suitable for candidates comfortable with tries and bitmasking, showing advanced optimization skills.
