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

#476 · #208 · Implement Trie (Prefix Tree)(实现 Trie（前缀树）)

📌 Problem Statement & Constraints

Implement a trie (prefix tree) with insert(word), search(word) and startsWith(prefix). Constraints: 1 <= word.length, prefix.length <= 2000; lowercase letters; at most 3 * 10^4 calls.

💡 Core Algorithmic Approaches

  1. A trie is a tree where each edge is a character and each node represents a prefix.
  2. Nested dictionaries are the simplest representation: node[char] descends, and a sentinel key marks the end of a word.
  3. The sentinel is essential: without it, search("app") would succeed merely because "apple" was inserted.
  4. All three operations are O(length of the input).

💻 Benchmark Python3 Implementation

class Trie:
    def __init__(self):
        self.root = {}                     # nested dicts; '#' marks a word end

    def insert(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:
        node = self.root
        for ch in word:
            if ch not in node:
                return False
            node = node[ch]
        return "#" in node                 # must be a complete word, not a prefix

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for ch in prefix:
            if ch not in node:
                return False
            node = node[ch]
        return True                        # any node reached is a valid prefix

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(L) per operation, where L is the length of the input string.
💾 Space Complexity
O(total characters inserted) for the trie.

⚠️ Interview Pitfalls & Follow-ups

  • Omitting the end-of-word marker: search would accept any prefix of an inserted word.
  • Using a fixed-size array of 26 children: it works but wastes memory for sparse tries; a dict adapts.
  • Confusing search with startsWith: the former requires a word end, the latter only a valid path.
  • Storing the full word at every node: unnecessary for this API.