💬 Discord
Sign In
NeetCode #477LC-211MediumTriesBlind 75NC 150NC 250
← Back to All Problems

#477 · #211 · Design Add and Search Words Data Structure(添加与搜索单词 - 数据结构设计)

📌 Problem Statement & Constraints

Design a data structure supporting addWord(word) and search(word), where search may contain . matching any single letter. Constraints: 1 <= word.length <= 25; lowercase letters and .; at most 10^4 calls.

💡 Core Algorithmic Approaches

  1. The trie is the same as for a plain prefix tree, with an end-of-word marker.
  2. search must branch at each ., exploring every child at that position.
  3. So the search becomes a DFS over the trie, consuming one character of the pattern per level.
  4. The . case is the only branch point, so the worst case is bounded by the number of trie nodes.

💻 Benchmark Python3 Implementation

class WordDictionary:
    def __init__(self):
        self.root = {}

    def addWord(self, word: str) -> None:
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node["#"] = True                   # end-of-word marker

    def search(self, word: str) -> bool:
        def dfs(node: dict, i: int) -> bool:
            if i == len(word):
                return "#" in node         # must end at a complete word
            ch = word[i]
            if ch == ".":                  # wildcard -> try every child
                return any(dfs(child, i + 1)
                           for key, child in node.items() if key != "#")
            if ch not in node:
                return False
            return dfs(node[ch], i + 1)

        return dfs(self.root, 0)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(L) for addWord; O(26^dots * L) worst case for search, but bounded by the number of trie nodes.
💾 Space Complexity
O(total characters) for the trie plus O(L) recursion.

⚠️ Interview Pitfalls & Follow-ups

  • Iterating over node.items() including the # marker: the marker is not a character, so it must be excluded from the wildcard branch.
  • Checking '#' in node before consuming all characters: a prefix would be accepted.
  • Storing words in a list and doing a linear scan: O(n * L) per search instead of a trie walk.
  • Treating . as matching zero characters: it matches exactly one.