Problem 61 · Strings & Tries

Implement Trie

MediumClassic DSA & systems

01Problem

Implement a prefix tree supporting insert(word), search(word) for exact match, and starts_with(prefix).

02Key insight

Each node maps a character to a child plus an end-of-word flag; every operation is a single walk of length L, independent of how many words are stored.

03Solution

solution.pypython35 lines

from __future__ import annotations


class TrieNode:
    __slots__ = ("children", "is_word")

    def __init__(self) -> None:
        self.children: dict[str, TrieNode] = {}
        self.is_word = False


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

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

    def _walk(self, s: str) -> TrieNode | None:
        node = self.root
        for ch in s:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

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

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

Try it first.

TimeO(L) per op

SpaceO(total chars)

tests.py · 4 passing

tests.pypython7 lines

t = Trie()
t.insert("apple")
assert t.search("apple") and not t.search("app")
assert t.starts_with("app") and not t.starts_with("b")
t.insert("app")
assert t.search("app")
assert t.starts_with("")

04Staff-level follow-up

How do you cut memory for millions of keys? Use a radix/compressed trie (merge single-child chains) or a DAWG / double-array trie; children as sorted arrays instead of dicts.