March 24
Design Add and Search Words Data Structure
How to use a Trie with DFS to support the . wildcard through controlled branching.
Trie Intermediate 25 min TypeScript
Design a structure that supports:
addWord(word)search(word)
search must accept . as a wildcard that matches exactly one character.
In the original problem, this is usually a class. In the SeniorPath playground, use:
operations: the list of operationsvalues: the word associated with each operation, ornullwhen there is none
Return an array with the result of each operation. Operations that do not return a value should return null.
Example:
Input:
operations = ["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
values = [null,"bad","dad","mad","pad","bad",".ad","b.."]
Output:
[null,null,null,null,false,true,true,true]
What to notice before coding
- The `.` wildcard stands for one single character, not for any whole suffix.
- The problem gets better when you think in shared prefixes, not in a loose list of words.
- Once `.` appears, the search stops being a straight walk and becomes branching from the current trie node.
Common mistakes
- storing everything in an array and comparing every word on every search
- treating `.` as "any remaining suffix" instead of "any single character"
Step 1 - Understand why an array is a weak baseline
If you store all words in a list, addWord is easy.
But search becomes:
- loop through every word
- compare character by character
- treat
.as a special case
It works, but search gets worse as the dictionary grows.
Step 2 - Ask what the problem wants to reuse
Words share prefixes all the time:
badbagbat
They all share the prefix ba.
If you store that prefix once, the structure gets smarter.
Step 3 - Arrive at the trie
In a Trie:
- each edge represents one character
- each node represents a prefix
- a marker tells you whether that node closes a complete word
addWord walks character by character and creates children when needed.
Step 4 - Understand why wildcard needs DFS
When the character is normal, search knows exactly which child to follow.
When the character is ., it must try every possible child from that node.
That turns search into a small DFS over the trie.
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function runWordDictionary(operations, values) {
// operations example: ["WordDictionary", "addWord", "search"]
// values example: [null, "bad", ".ad"]
// your solution here
return []
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(word.length) for addWord; search depends on how many trie nodes wildcards force you to explore
Space: O(total inserted characters)
Solution 1 - Word array with linear search
Good baseline because it solves the problem without changing the data structure.
export function runWordDictionary(operations, values) {
const words = []
const result = []
function matches(pattern, word) {
if (pattern.length !== word.length) {
return false
}
for (let index = 0; index < pattern.length; index += 1) {
if (pattern[index] !== "." && pattern[index] !== word[index]) {
return false
}
}
return true
}
for (let index = 0; index < operations.length; index += 1) {
const operation = operations[index]
const value = values[index]
if (operation === "WordDictionary") {
result.push(null)
} else if (operation === "addWord") {
words.push(value)
result.push(null)
} else if (operation === "search") {
result.push(words.some((word) => matches(value, word)))
}
}
return result
}It works.
But every search scans the whole list, even when many words share prefixes.
Solution 2 - Trie plus DFS for wildcard search
Now the structure matches the problem:
addWordwalks down the trie creating nodessearchis guided by the pattern.branches, but only from the current node
type TrieNode = {
children: Map<string, TrieNode>
isWord: boolean
}
function createNode(): TrieNode {
return {
children: new Map(),
isWord: false,
}
}
export function runWordDictionary(operations, values) {
const root = createNode()
const result = []
function addWord(word: string) {
let node = root
for (const char of word) {
if (!node.children.has(char)) {
node.children.set(char, createNode())
}
node = node.children.get(char)!
}
node.isWord = true
}
function search(word: string): boolean {
function dfs(node: TrieNode, index: number): boolean {
if (index === word.length) {
return node.isWord
}
const char = word[index]
if (char !== ".") {
const next = node.children.get(char)
return next ? dfs(next, index + 1) : false
}
for (const next of node.children.values()) {
if (dfs(next, index + 1)) {
return true
}
}
return false
}
return dfs(root, 0)
}
for (let index = 0; index < operations.length; index += 1) {
const operation = operations[index]
const value = values[index]
if (operation === "WordDictionary") {
result.push(null)
} else if (operation === "addWord") {
addWord(value)
result.push(null)
} else if (operation === "search") {
result.push(search(value))
}
}
return result
}The strong point is not only “use a trie”.
It is noticing that wildcard does not mean “compare everything”.
It means “branch only when the pattern actually forces branching”.
What to say in the interview
A good short explanation would be:
The baseline keeps words in an array and compares everything character by character on each search. That works, but it ignores shared prefixes. The stronger version uses a trie to store those prefixes once. In
search, a normal character follows one child and.becomes a DFS across the children of the current node. That way the structure matches the rule of the problem.
That shows that you:
- picked the right structure for prefix sharing
- understood the cost of wildcard branching
- explained why DFS appears
- adapted a class-style API to the playground format
When this pattern shows up again
The same idea comes back when the problem asks for:
- prefix lookup
- autocomplete
- word dictionaries
- single-character wildcard matching
If the central question is “how do I reuse common prefixes?”, trie becomes a strong candidate.