Design Add and Search Words Data Structure (LeetCode 211)

The problem

Design a WordDictionary with two methods:

• addWord(word) stores a word of lowercase letters.
• search(word) returns True if some stored word matches. The pattern may contain ., which matches any one letter.

addWord("bad"); addWord("dad"); addWord("mad")
search("pad") -> False
search("bad") -> True
search(".ad") -> True
search("b..") -> True

.ad matches bad, dad and mad; b.. matches bad; nothing stored starts with p.

How to think about it

Start with brute force. Keep a list of words. For each search, compare the pattern against every word of the same length, letter by letter, treating . as “anything”. That is O(N·L) per search for N words. With many words and many searches, it is too slow.

The key insight: a trie lets most letters prune the search. Store the words in a trie, exactly as in Implement Trie. A normal letter means one child to follow, so most of the stored words are ruled out at once. Only a . is different: it can be any letter, so you try every child and succeed if any branch succeeds.

That makes search a DFS. The state is “which node am I at, and which character of the pattern am I matching?” Write dfs(node, i). When i reaches the end of the pattern, you match only if a word ends here ('$' in the node). A letter recurses into one child; a dot recurses into all of them.

Which pattern is this? Trie plus backtracking DFS. The tell is “dictionary of words” plus “wildcard in the query”. addWord is the plain trie insert; all the work is in search.

Approach

1. addWord: standard trie insert into a dict of dicts, setting '$' at the end.
2. search(w) calls dfs(root, 0).
3. In dfs(n, i): if i == len(w), return '$' in n.
4. If w[i] is ., return True if dfs(child, i + 1) is True for any child key other than '$'.
5. Otherwise, return True only if w[i] is a child and dfs(n[w[i]], i + 1) is True.

Solution

class WordDictionary:
    def __init__(self): self.root = {}
    def addWord(self, w):
        n = self.root
        for c in w: n = n.setdefault(c, {})
        n['$'] = True
    def search(self, w):
        def dfs(n, i):
            if i == len(w): return '$' in n          # pattern used up
            c = w[i]
            if c == '.':                             # wildcard: try every child
                return any(dfs(n[k], i + 1) for k in n if k != '$')
            return c in n and dfs(n[c], i + 1)       # letter: one child only
        return dfs(self.root, 0)
# add "bad","dad","mad"; search(".ad") -> True; search("b..") -> True; search("pad") -> False

Dry run

After adding bad, dad and mad, the root has children b, d, m. Tracing search(".ad"):

any short-circuits on the first True, so d and m are never explored. The other searches return search("b..") -> True, search("pad") -> False, search("....") -> False (no four-letter word) and search(".") -> False.

Complexity

• Time: O(L) for a pattern with no dots, one lookup per character. With dots, each . can branch into up to 26 children, so a pattern with k dots can cost O(26^k) in the worst case, still bounded by the size of the trie.
• Space: O(S) for the trie (S total characters added), plus O(L) recursion depth for a search.

Edge cases and pitfalls

• Skip the sentinel when fanning out on .. Recursing into n['$'] would crash, because True is not a dict.
• Length matters. "ba" must not match "bad". The '$' check at the end handles this.
• All dots ("...") is the worst case: it explores every word of that length.
• Building a regex or scanning all words per search is the common wrong approach: correct, but O(N·L) per call.

Related problems

• Implement Trie (Prefix Tree) (LeetCode 208): the same structure without wildcards.
• Word Search II (LeetCode 212): another DFS guided by a trie, this time over a grid.
• Word Search (LeetCode 79): the backtracking DFS this search resembles.