How do you solve Design Add and Search Words Data Structure?

Implement a TrieNode class with a dictionary of children and an end_of_word flag. For addWord, insert characters sequentially, creating nodes as needed. For search, use a recursive DFS that, at each character, either follows the exact child node or, if '.', recursively explores all children. Return true if any path matches the entire word and ends at a node marked as end_of_word.

What pattern does Design Add and Search Words Data Structure use?

The Pattern: Trie (Prefix Tree) with Backtracking for Wildcard Search The Heuristic: When searching with wildcards in a prefix tree, use DFS to explore all possible child nodes at wildcard positions, enabling flexible pattern matching while leveraging prefix sharing for efficiency.

Design Add and Search Words Data Structure

Q: What is the time complexity of Design Add and Search Words Data Structure?

O(m * 26^k). In the worst case, the search explores all possible branches for each '.' wildcard, where m is the length of the word and k is the number of wildcards. Each wildcard can branch into up to 26 children, leading to exponential branching in k. However, typical usage and pruning make this efficient in practice.

Problem

Design a data structure that supports adding new words and searching for a word, where the search word may contain the dot character '.' to represent any one letter.

1 ≤ word.length ≤ 500
word in addWord consists of lowercase English letters
word in search consists of '.' or lowercase English letters
At most 3 * 10⁴ calls will be made to addWord and search

Example

Input: addWord("bad"), addWord("dad"), addWord("mad"), search("pad"), search("bad"), search(".ad"), search("b..")

Output: [null, null, null, false, true, true, true]

Words "bad", "dad", and "mad" are added to the data structure. Searching for "pad" returns false because it was not added. Searching for "bad" returns true as it was added. Searching for ".ad" returns true because '.' matches any letter and "bad", "dad", and "mad" all match. Searching for "b.." returns true because it matches "bad".

Approach

Straightforward Solution

A brute-force approach would store all words in a list and check each word against the search pattern, which is inefficient (O(n*m) where n is number of words and m is word length) and does not scale well.

Core Observation

A Trie is a tree-like data structure that stores words by sharing common prefixes, enabling efficient prefix-based queries. The wildcard '.' introduces branching in the search, requiring exploration of all possible child nodes at that position.

Path to Optimal

Preview

The key recognition signals are 'add words' and 'search with wildcard .', which indicate a Trie data structure with backtracking search…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Implement a TrieNode class with a dictionary of children and an end_of_word flag. For addWord, insert characters sequentially, creating nodes as needed…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(m * 26^k)

In the worst case, the search explores all possible branches for each '.' wildcard, where m is the length of the word and k is the number of wildcards. Each wildcard can branch into up to 26 children, leading to exponential branching in k. However, typical usage and pruning make this efficient in practice.

Space

O(n * m)

The Trie stores all added words, with each character represented as a node. In the worst case, all words are distinct with no shared prefixes, leading to O(n*m) nodes, where n is the number of words and m is the average word length.

Solution

Python

1class TrieNode:
  def __init__(self):
      self.children = {}
      self.end_of_word = False
5
6class WordDictionary:
  def __init__(self):
      self.root = TrieNode()
9
  def addWord(self, word: str) -> None:
      curr = self.root
      for c in word:
          if c not in curr.children:
              curr.children[c] = TrieNode()
          curr = curr.children[c]
      curr.end_of_word = True
17
  def search(self, word: str) -> bool:
      def dfs(j, root):
          curr = root
          for i in range(j, len(word)):
              c = word[i]
              if c == ".":
                  for child in curr.children.values():
                      if dfs(i + 1, child):
                          return True
                  return False
              else:
                  if c not in curr.children:
                      return False
                  curr = curr.children[c]
          return curr.end_of_word
33
      return dfs(0, self.root)

Step-by-Step Solution

1

Build Trie Nodes and Insert Words to Share Prefixes

3self.children = {}
4self.end_of_word = False
8self.root = TrieNode()
11curr = self.root
12for c in word:
13    if c not in curr.children:
14        curr.children[c] = TrieNode()
15    curr = curr.children[c]
16curr.end_of_word = True

Objective

To construct a prefix tree that stores all added words efficiently by sharing common prefixes.

Key Insight

A TrieNode holds a dictionary of children nodes keyed by characters and a flag indicating if a word ends at that node. Adding a word involves traversing or creating nodes for each character, enabling fast prefix-based storage and lookup. This structure reduces redundant storage and accelerates searches compared to a flat list.

Interview Quick-Check

Core Logic

Each character in the word corresponds to a child node in the Trie, creating a path that represents the word.

State & Boundaries

Marking the end_of_word flag at the last character node distinguishes complete words from prefixes.

Common Pitfalls & Bugs

Forgetting to create a new TrieNode when a character is not present leads to incorrect or incomplete Trie construction.

2

Explore Trie Recursively to Match Words with Wildcards

To perform a depth-first search on the Trie that supports '.' wildcard matching by exploring all possible child nodes at wildcard positions.

1 more step with full analysis available on Pro.

Line Analysis

This solution has 5 Critical lines interviewers watch for.

Line 16 Critical

curr.end_of_word = True

Mark the current node as the end of a word after insertion.

This line is critical because it distinguishes complete words from mere prefixes, enabling accurate search results that differentiate between partial and full matches.

Line 23 Critical

if c == ".":

Check if the current character is a wildcard '.'

This conditional is the core of wildcard handling; it forces exploration of all children nodes, which is essential to correctly match any letter at this position.

Line 25 Critical

if dfs(i + 1, child):

Recursively search the remainder of the word from the next index and child node.

This recursive exploration is the heart of the backtracking search, enabling the algorithm to find any valid word matching the pattern by trying all possible continuations.

Full line-by-line criticality + rationale for all 24 lines available on Pro.

Test Your Understanding

Why does the search function use DFS and explore all children when encountering a '.' character?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Design Add and Search Words Data Structure from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Design Add and Search Words Data Structure drill

or drill a free problem

1	`class TrieNode:`
2	`def __init__(self):`
3	`self.children = {}`
4	`self.end_of_word = False`
5
6	`class WordDictionary:`
7	`def __init__(self):`
8	`self.root = TrieNode()`
9
10	`def addWord(self, word: str) -> None:`
11	`curr = self.root`
12	`for c in word:`
13	`if c not in curr.children:`
14	`curr.children[c] = TrieNode()`
15	`curr = curr.children[c]`
16	`curr.end_of_word = True`
17
18	`def search(self, word: str) -> bool:`
19	`def dfs(j, root):`
20	`curr = root`
21	`for i in range(j, len(word)):`
22	`c = word[i]`
23	`if c == ".":`
24	`for child in curr.children.values():`
25	`if dfs(i + 1, child):`
26	`return True`
27	`return False`
28	`else:`
29	`if c not in curr.children:`
30	`return False`
31	`curr = curr.children[c]`
32	`return curr.end_of_word`
33
34	`return dfs(0, self.root)`

3	`self.children = {}`
4	`self.end_of_word = False`
8	`self.root = TrieNode()`
11	`curr = self.root`
12	`for c in word:`
13	`if c not in curr.children:`
14	`curr.children[c] = TrieNode()`
15	`curr = curr.children[c]`
16	`curr.end_of_word = True`