Implement Trie

Signal

Any time you need fast prefix lookups over a growing set of words — not just "is this exact word present" but "does anything start with this" — a hash map of full strings can't answer the prefix question efficiently. Build a prefix tree: each node is one character step shared by every word that agrees up to that point.

Approach

Each node holds a map from character to child node, plus a flag marking whether a word ends exactly there. Insert walks the word character by character, creating child nodes as needed, and marks the final node as a word end. Search walks the same way but requires the end-of-word flag at the final node. Prefix search is identical to search except it doesn't check that flag — just that the path exists.

Skeleton

node = root
for ch in word:
    node = node.children[ch]  # create if missing, on insert
return node.is_end            # search: True/False; prefix: skip this check

Solution

class TrieNode:
    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.is_end = False


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True

    def _walk(self, prefix: str) -> TrieNode | None:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

    def search(self, word: str) -> bool:
        node = self._walk(word)
        return node is not None and node.is_end

    def starts_with(self, prefix: str) -> bool:
        return self._walk(prefix) is not None

Complexity

O(L) time per operation, where L is the word/prefix length — each step is one dict lookup. O(total characters inserted) space in the worst case (no shared prefixes).

Pitfalls

• Confusing search and starts_with — forgetting the is_end check makes search behave like a prefix check and return false positives (e.g. search("app") returning True just because "apple" was inserted).
• Using a fixed 26-length array per node is faster for lowercase-only inputs but breaks the moment the alphabet isn't guaranteed — a dict is the safer default unless the constraints pin down the character set.
• Re-walking from self.root on every call is correct but means insert/search share no state across calls other than the tree itself — don't try to cache a "current node" between calls, the API is stateless per call.