LeetEye LeetEye
Medium Trie ~5 min

Design Add and Search Words Data Structure

tries design-add-and-search-words-data-structure

Problem

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:
- WordDictionary() Initializes the object.
- void addWord(word) Adds word to the data structure, it can be matched later.
- bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots . where dots can be matched with any letter.

Examples

Example 1
Input: ["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
Output: [null,null,null,null,false,true,true,true]
Key Insight

Standard trie insert. For search, when we hit `.`, try ALL children recursively.

Standard trie, but search uses DFS. At `.`, recurse on ALL children. At regular char, follow that path only. Return true if any path reaches is_end.

How to Approach This Problem

Pattern Recognition: When you see keywords like design add and search words data structure tries, think Trie.

Step-by-Step Reasoning

1 Adding a word with dots like "a.c":
Answer: Is not supported in this problem
Only search has wildcards. Words added are normal strings.
2 Searching "bad" (no dots):
Answer: Uses standard trie search
No wildcards = normal trie traversal.
3 The dot . matches:
Answer: Any single character
Like regex ., it matches exactly one character, any character.
4 To search ".ad" in a trie:
Answer: Try all children of root, continue with "ad"
First character is ., so we try 'a', 'b', 'c', ... all 26 possibilities for first character.
5 When we hit a .:
Answer: Recurse on ALL children with remaining pattern
Each child is a valid match for .. If any path succeeds, return true.
6 Searching "..." (all dots) in worst case:
Answer: O(26^m) - exponential
Each dot branches to 26 children. m dots = 26^m paths to explore.

Solution

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

class WordDictionary:
    def __init__(self):
        self.root = TrieNode()
    
    def addWord(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
    
    def search(self, word: str) -> bool:
        def dfs(index, node):
            if index == len(word):
                return node.is_end
            
            char = word[index]
            if char == '.':
                # Try all children
                for child in node.children.values():
                    if dfs(index + 1, child):
                        return True
                return False
            else:
                if char not in node.children:
                    return False
                return dfs(index + 1, node.children[char])
        
        return dfs(0, self.root)

Complexity Analysis

Time O(m) add, O(26^m) search worst
Space O(total chars)

Master This Pattern

Build intuition with interactive MCQs. Practice Trie problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye