Design Add and Search Words Data Structure

Free with account Updated Nov 19, 2026 · 6 min read
On this page

    Problem statement

    Design a word dictionary with two operations. addWord(word) stores a lowercase word. search(pattern) returns true if any stored word matches the pattern exactly, where each . in the pattern matches any single letter. The match must cover the whole word, not just a prefix.

    A trie question with one twist: the wildcard turns a single walk down the tree into a small search over several branches. The same shape appears in autocomplete with typos, crossword solvers and log-pattern filters. Original problem: LeetCode 211.

    Example

    The three words share the prefix "ca", so they share two trie nodes; yellow nodes end a word.
    The three words share the prefix "ca", so they share two trie nodes; yellow nodes end a word.
    addWord("cache"); addWord("cast"); addWord("cat")
    search("ca.")    -> true     # cat
    search("c..t")   -> true     # cast
    search(".a.he")  -> true     # cache
    search("ca")     -> false    # "ca" is only a prefix
    search("dog")    -> false

    Constraints (assumed)

    • Words have 1 to 25 lowercase letters; up to 10⁴ calls.
    • A pattern has at most 2 dots (the cost of a search grows with the number of dots).

    What this question tests

    • Choosing a trie so that words sharing a prefix share work.
    • Turning the wildcard into a DFS / backtracking over children.
    • The end-of-word flag: matching a prefix is not matching a word.

    Questions to ask first

    1. What characters can appear? (Here: lowercase letters, plus . in patterns.)
    2. Must the pattern match the whole word? (Here: yes.)
    3. How many dots can a pattern have? That bounds the branching.
    4. Is it read-heavy or write-heavy? That decides whether to index words by length or build extra structures.