Design Add and Search Words Data Structure

▶

Steps

setup

Initialize Trie Root

Create the root node of the trie, which is empty and not an end of any word.

💡 The root node is the starting point for all insertions and searches.

Line:

self.root = TrieNode()

💡 The trie starts empty with a single root node.

insert

Insert 'b' of 'bad'

Insert the first character 'b' of the word 'bad' by adding a child node to the root.

💡 Each character is added as a child node if it does not exist.

Line:

if ch not in node.children:
    node.children[ch] = TrieNode()

💡 New branches are created for characters not yet in the trie.

insert

Insert 'a' of 'bad'

Insert the second character 'a' as a child of node 'b'.

💡 Continue adding nodes for each character in the word.

Line:

if ch not in node.children:
    node.children[ch] = TrieNode()

💡 Trie branches grow deeper as words are inserted.

insert

Insert 'd' of 'bad' and mark end

Insert the last character 'd' and mark this node as end of word.

💡 Marking end_of_word signals a complete word in the trie.

Line:

if ch not in node.children:
    node.children[ch] = TrieNode()
node.is_end = True

💡 End markers distinguish prefixes from complete words.

insert

Insert 'dad' sharing 'a' and 'd'

Insert 'dad' by adding 'd' child to root, then adding 'a' and 'd' nodes as new children.

💡 Trie nodes are shared when prefixes overlap, but here 'dad' shares only 'a' and 'd' nodes under new 'd' root child.

Line:

if ch not in node.children:
    node.children[ch] = TrieNode()

💡 Trie efficiently stores overlapping prefixes once.

insert

Insert 'mad' sharing 'a' and 'd'

Insert 'mad' by adding 'm' child to root, then adding 'a' and 'd' nodes as new children.

💡 New branches start at root for different first letters.

Line:

if ch not in node.children:
    node.children[ch] = TrieNode()

💡 Trie branches represent distinct first letters.

search

Search 'pad' - start at root

Start searching for 'pad' from the root node with index 0.

💡 Search uses a stack to track nodes and indices to explore.

Line:

stack = [(0, self.root)]

💡 Search begins at root with first character index.

search

Search 'pad' - check 'p' at root

Pop root and index 0 from stack, check if 'p' child exists.

💡 If character exists as child, push child with next index.

Line:

if ch in node.children:
    stack.append((index + 1, node.children[ch]))

💡 No matching branch for 'p' means search will fail.

search

Search 'bad' - start at root

Start searching for 'bad' from root with index 0.

💡 Reset stack for new search word.

Line:

stack = [(0, self.root)]

💡 Search begins fresh for 'bad'.

search

Search 'bad' - follow 'b' child

Pop root and index 0, find 'b' child, push node 'b' with index 1.

💡 Follow exact character match in trie.

Line:

if ch in node.children:
    stack.append((index + 1, node.children[ch]))

💡 Search path advances along 'b'.

search

Search 'bad' - follow 'a' child

Pop node 'b' and index 1, find 'a' child, push node 'a' with index 2.

💡 Continue following exact characters.

Line:

if ch in node.children:
    stack.append((index + 1, node.children[ch]))

💡 Search path continues deeper.

search

Search 'bad' - follow 'd' child and check end

Pop node 'a' and index 2, find 'd' child, push node 'd' with index 3 (end of word).

💡 At word end, check if node marks end of word.

Line:

if index == len(word):
    if node.is_end:
        return True

💡 Exact match found for 'bad'.

search

Search '.ad' - start at root with wildcard

Start searching '.ad' from root with index 0; first char is '.', so push all children with index 1.

💡 Wildcard '.' means explore all children nodes.

Line:

if ch == '.':
    for child in node.children.values():
        stack.append((index + 1, child))

💡 Wildcard expands search paths to all possible branches.

search

Search '.ad' - follow 'b' branch for 'a'

Pop node 'b' and index 1, check character 'a', push node 'a' with index 2.

💡 Follow exact character after wildcard expansion.

Line:

if ch in node.children:
    stack.append((index + 1, node.children[ch]))

💡 Search narrows down after wildcard.

search

Search '.ad' - follow 'd' child and check end

Pop node 'a' and index 2, check 'd' child, push node 'd' with index 3 (end of word).

💡 At word end, verify if node marks end of word.

Line:

if index == len(word):
    if node.is_end:
        return True

💡 Wildcard search successfully matched 'bad'.

search

Search 'b..' - start at root with 'b'

Start searching 'b..' from root, push node 'b' with index 1.

💡 Exact character match for first letter.

Line:

if ch in node.children:
    stack.append((index + 1, node.children[ch]))

💡 Search path begins with 'b'.

search

Search 'b..' - wildcard at index 1

Pop node 'b' and index 1, character is '.', push all children of 'b' with index 2.

💡 Wildcard expands search to all children nodes.

Line:

if ch == '.':
    for child in node.children.values():
        stack.append((index + 1, child))

💡 Search explores all possible next characters.

search

Search 'b..' - wildcard at index 2

Pop node 'a' and index 2, character is '.', push all children of 'a' with index 3.

💡 Wildcard again expands search to all children nodes.

Line:

if ch == '.':
    for child in node.children.values():
        stack.append((index + 1, child))

💡 Search reaches possible word ends.

search

Search 'b..' - check end of word at index 3

Pop node 'd' and index 3, index equals word length, check if node is end of word.

💡 If node is end, search returns true.

Line:

if index == len(word):
    if node.is_end:
        return True

💡 'b..' matches 'bad' in trie.

class TrieNode:
    def __init__(self):
        self.children = {}  # STEP 1
        self.is_end = False

class WordDictionary:
    def __init__(self):
        self.root = TrieNode()  # STEP 1

    def addWord(self, word: str) -> None:
        node = self.root
        for i, ch in enumerate(word):  # STEP 2-6
            if ch not in node.children:
                node.children[ch] = TrieNode()  # Insert new node
            node = node.children[ch]
        node.is_end = True  # Mark end of word

    def search(self, word: str) -> bool:
        stack = [(0, self.root)]  # STEP 7,9,13,16
        while stack:
            index, node = stack.pop()
            if index == len(word):
                if node.is_end:
                    return True  # STEP 12,15,19
                continue
            ch = word[index]
            if ch == '.':
                for child in node.children.values():
                    stack.append((index + 1, child))  # STEP 13,17,18
            else:
                if ch in node.children:
                    stack.append((index + 1, node.children[ch]))  # STEP 8,10,11,14,16
        return False  # STEP 8

wd = WordDictionary()
wd.addWord("bad")  # STEPS 2-4
wd.addWord("dad")  # STEP 5
wd.addWord("mad")  # STEP 6
print(wd.search("pad"))  # STEP 7-8
print(wd.search("bad"))  # STEP 9-12
print(wd.search(".ad"))  # STEP 13-15
print(wd.search("b.."))  # STEP 16-19

📊

Design Add and Search Words Data Structure - Watch the Algorithm Execute, Step by Step

Watching each character insertion and each search decision visually reveals how tries efficiently store and query words, especially with wildcards.

insert

insert

bad

b

insert

bad

ba

insert

bad

ad*

insert

dad

dad*

insert

mad

mad*

search

pad

search

pad

Search: false

search

bad

search

bad

b

search

bad

a

search

bad

d*

Search: true

search

.ad

bdm

search

.ad

ba

search

.ad

d*

Search: true

search

b..

b

search

b..

a

search

b..

d*

search

b..

d*

Search: true

Key Takeaways

✓ Trie nodes efficiently share prefixes, reducing redundant storage.

This is hard to see from code alone but clear when watching nodes and edges build.

✓ Search with '.' wildcard expands to multiple branches, handled via stack.

Visualizing stack pushes for '.' clarifies how multiple paths are explored.

✓ End of word markers are critical to distinguish prefixes from complete words.

Seeing when search returns true only at end nodes helps understand correctness.

Practice

1. Given the following code snippet for finding concatenated words, what is the value of memo after calling dfs('catsdog', 0) on the input ['cat', 'cats', 'dog', 'catsdog']?

easy

A. {0: True, 3: True, 4: True, 7: True}

B. {0: True, 3: True, 4: False}

C. {0: True, 3: False, 4: True}

D. {0: False, 3: True, 4: True}

Solution

1. Step 1: Trace dfs('catsdog', 0) calls and memo updates

   Start=0: check prefixes 'cat'(0-3), 'cats'(0-4). 'cat' leads to dfs(3), 'cats' leads to dfs(4).

2. Step 2: Evaluate dfs(3) and dfs(4)

   dfs(3) checks 'sdog' prefix - no match, returns False; dfs(4) checks 'dog' prefix - matches 'dog', dfs(7) returns True; memo[4]=True, memo[3]=False, memo[0]=True.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Memo correctly records True at 0 and 4, False at 3 [OK]

Hint: Memo stores start indices where suffix can form concatenation [OK]

Common Mistakes:

• Confusing indices or forgetting to memoize False results

2. Consider the following Python code implementing the bitwise trie approach to find maximum XOR of two numbers. Given the input nums = [2, 5], what is the value of current_xor after processing the number 5 in the second loop?

easy

A. 3

B. 6

C. 7

D. 5

Solution

1. Step 1: Trace bits of number 5

   5 in binary (32-bit) ends with bits ...00000101. We check bits from 31 down to 0.

2. Step 2: Traverse trie to maximize XOR

   For each bit, we try to go to the opposite bit in trie. For 5, the best XOR partner is 2 (binary 10). XOR of 5 and 2 is 7, so current_xor accumulates bits where toggled bit exists, resulting in 7.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Maximum XOR of 2 and 5 is 7, which matches current_xor after processing 5 [OK]

Hint: XOR bits accumulate where opposite bit exists [OK]

Common Mistakes:

• Confusing final max_xor with current_xor at iteration

3. You are given a 2D grid of letters and a list of words. You need to find all words from the list that can be formed by sequentially adjacent letters on the board, where adjacent letters are horizontally or vertically neighboring. Each letter cell may only be used once per word. Which algorithmic approach is best suited to efficiently solve this problem when the word list is large?

easy

A. Build a Trie from the word list and perform a single DFS on the board with prefix pruning using the Trie.

B. Use a brute force DFS for each word independently, checking all paths on the board.

C. Use dynamic programming to store subproblems of partial word matches on the board.

D. Sort the words and use binary search combined with DFS to find matches on the board.

Solution

1. Step 1: Understand problem constraints and prefix sharing

   Multiple words need to be found on the board, and many words may share prefixes, making prefix pruning beneficial.

2. Step 2: Use Trie for efficient prefix pruning during DFS

   Building a Trie allows pruning DFS paths early if no word starts with the current prefix, avoiding redundant searches and improving efficiency.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Trie + DFS reduces search space drastically compared to checking each word separately [OK]

Hint: Trie + DFS prunes invalid prefixes early [OK]

Common Mistakes:

• Thinking brute force DFS per word is efficient
• Assuming DP applies here
• Using sorting and binary search without prefix pruning

4. Consider the following buggy code snippet for the longest word in dictionary problem. Which line contains the subtle bug that can cause incorrect results?

medium

A. Line: queue.append(child) without checking if child.word is not None

B. Line: for ch in sorted(node.children.keys())

C. Line: node.word = word in insert method

D. Line: trie.insert(word) in the for loop

Solution

1. Step 1: Identify enqueue condition

   The BFS queue should only include nodes representing complete words (child.word != None) to ensure all prefixes are valid.

2. Step 2: Locate the bug

   The code enqueues all children regardless of whether they represent complete words, allowing invalid prefixes to be considered, breaking the prefix condition.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Enqueueing invalid prefix nodes causes incorrect longest word [OK]

Hint: Only enqueue nodes with complete words in BFS [OK]

Common Mistakes:

• Enqueueing all children regardless of word completion
• Misplacing word assignment in insert
• Sorting children incorrectly

5. Suppose the autocomplete system must now support returning the top 5 suggestions instead of 3, and the products list can be updated dynamically with insertions. Which modification to the trie-based approach is most appropriate to maintain efficient queries?

hard

A. Increase the suggestions list size to 5 at each node and rebuild the entire trie after each insertion.

B. Store all products at each node and filter top 5 suggestions during query time.

C. Switch to brute force filtering and sorting after each insertion to avoid trie complexity.

D. Use a balanced search tree or heap at each node to maintain top 5 suggestions dynamically during insertions.

Solution

1. Step 1: Understand dynamic updates and top-K requirement

   Supporting dynamic insertions and top 5 suggestions requires efficient updates and queries without rebuilding the entire trie.

2. Step 2: Evaluate data structures for suggestions

   Using a balanced tree or min-heap at each node allows maintaining top 5 suggestions dynamically as products are inserted, avoiding costly rebuilds.

3. Step 3: Reject naive approaches

   Rebuilding trie after each insertion is inefficient. Brute force filtering is too slow. Storing all products at each node wastes space and slows queries.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Balanced structures enable efficient dynamic top-K maintenance [OK]

Hint: Use balanced structures at nodes for dynamic top-K updates [OK]

Common Mistakes:

• Rebuilding trie on every insertion
• Ignoring dynamic update costs
• Storing all products at nodes