Design Add and Search Words Data Structure

Difficulty: Medium Source: NeetCode

Problem

Design a data structure that supports adding new words and searching for whether a string matches any previously added string.

Implement the WordDictionary class:

• WordDictionary() Initializes the object.
• void addWord(word) Adds word to the data structure.
• 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.

Example 1: Input: ["WordDictionary","addWord","addWord","addWord","search","search","search","search"] with args [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]] Output: [null,null,null,null,false,true,true,true]

Constraints:

• 1 <= word.length <= 25
• word in addWord consists of lowercase English letters
• word in search consists of '.' or lowercase English letters
• At most 10^4 calls to addWord and search

Prerequisites

Before attempting this problem, you should be comfortable with:

• Trie (Prefix Tree) — the core data structure used here; review LeetCode 208 first
• DFS / Recursion — needed to handle the wildcard '.' by branching into all children
• Backtracking — the DFS explores and backtracks when a branch fails

1. Brute Force

Intuition

Store every added word in a list. For search, iterate through all stored words and check each one character by character, treating '.' as a match for anything. This is simple but search is O(W * L) where W is the number of stored words.

Algorithm

1. Keep a list of added words.
2. addWord(word): append to the list.
3. search(word): for each stored word of matching length, compare char by char — '.' always matches, letters must match exactly.

Solution

class WordDictionary:
    def __init__(self):
        self.words = []

    def addWord(self, word: str) -> None:
        self.words.append(word)

    def search(self, word: str) -> bool:
        for stored in self.words:
            if len(stored) != len(word):
                continue
            match = True
            for a, b in zip(stored, word):
                if b != '.' and a != b:
                    match = False
                    break
            if match:
                return True
        return False


wd = WordDictionary()
wd.addWord("bad")
wd.addWord("dad")
wd.addWord("mad")
print(wd.search("pad"))  # False
print(wd.search("bad"))  # True
print(wd.search(".ad"))  # True
print(wd.search("b.."))  # True

Complexity

• Time: O(W * L) per search where W = number of words, L = word length
• Space: O(W * L)

2. Trie with DFS for Wildcards

Intuition

Build a standard trie for addWord. For search, walk the trie character by character. When the character is a normal letter, follow the single matching child (or return False if it doesn’t exist). When it’s a '.', try every child and recursively search the rest of the word from each one — if any branch succeeds, return True. This is effectively DFS through the trie, branching only at wildcard positions.

Algorithm

1. Build a trie with TrieNode(children={}, is_end=False).
2. addWord(word): standard trie insert.
3. search(word): define a recursive helper dfs(node, index):
   • If index == len(word), return node.is_end.
   • Let ch = word[index].
   • If ch == '.': call dfs(child, index+1) for every child; return True if any succeeds.
   • Otherwise: if ch not in node.children return False; else recurse on node.children[ch].

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 ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word: str) -> bool:
        def dfs(node, i):
            if i == len(word):
                return node.is_end
            ch = word[i]
            if ch == '.':
                for child in node.children.values():
                    if dfs(child, i + 1):
                        return True
                return False
            else:
                if ch not in node.children:
                    return False
                return dfs(node.children[ch], i + 1)

        return dfs(self.root, 0)


wd = WordDictionary()
wd.addWord("bad")
wd.addWord("dad")
wd.addWord("mad")
print(wd.search("pad"))   # False
print(wd.search("bad"))   # True
print(wd.search(".ad"))   # True
print(wd.search("b.."))   # True
print(wd.search("..."))   # True  (matches bad/dad/mad)
print(wd.search("...."))  # False (no 4-letter words)

Complexity

• Time: O(L) for addWord; O(26^L) worst case for search (all dots), but typically much better
• Space: O(N * L) for the trie where N = number of words

Common Pitfalls

Forgetting to return False after the dot loop. After trying all children of a '.' node and none returning True, you must explicitly return False. Falling through without a return gives None, which is falsy but can cause subtle bugs.

Using is_end instead of recursing at the base case. At the base case i == len(word), you’re checking if a complete word ends here — don’t return True blindly; always check node.is_end.

Length mismatch with wildcards. A '.' matches exactly one character, not zero or many. Your recursion naturally enforces this since you always advance i by 1, but it’s easy to confuse '.' with a regex wildcard like .*.