{ }DevToolsDaily
ToolsInterview
Problems
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Design Add and Search Words – Solution & Complexity

Interview solutions
/
Design Add and Search Words

1. Recognize the Pattern

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

2. Build the Algorithm

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

3. Check Edge Cases

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

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)Combination Sum solution (medium)Find Median from Data Stream solution (hard)Letter Combinations of a Phone Number solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?