{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Design Add and Search Words – Solution & Complexity

Interview solutions
/
Design Add and Search Words

Solution Walkthrough

  1. Step 1: Recognize the Pattern

    The key pattern is: Trie search backtracks across children for wildcard positions. Identify the state and invariant before coding.

  2. Step 2: Build the Algorithm

    Advance one state transition at a time. Mark or update state before exploring dependent work.

  3. Step 3: Check Edge Cases

    Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.

  4. Step 4: Solution and Complexity

    Time: O(total add characters + wildcard search branches). Space: O(total inserted characters).

    def word_dictionary(operations: list[str], words: list[str]) -> list[int]:
    root, answer = {}, []
    def matches(node, word, index):
        if index == len(word): return "#" in node
        char = word[index]
        if char == ".": return any(matches(child, word, index + 1) for key, child in node.items() if key != "#")
        return char in node and matches(node[char], word, index + 1)
    for operation, word in zip(operations, words):
        if operation == "add":
            node = root
            for char in word: node = node.setdefault(char, {})
            node["#"] = {}
        else: answer.append(int(matches(root, word, 0)))
    return answer

FAQ

See also

Practice Design Add and Search Words online (run code in the browser)Implement Trie solution (medium)Word Search II solution (hard)Combination Sum solution (medium)Combination Sum II solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?