Trie

Prefix search, autocomplete and word-search problems.

A trie (prefix tree) stores strings character by character, so all words sharing a prefix share a path. Lookups and prefix checks take O(L) time, where L is the word length — independent of how many words are stored.

When to use it

Prefix queries: "does any word start with…", autocomplete
Searching many words at once, e.g. finding all dictionary words in a grid
Word games and spell-checkers
Longest common prefix

Implementation

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

    def __init__(self):
        self.children = {}
        self.is_word = False


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

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

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

    def search(self, word):
        node = self._walk(word)
        return bool(node and node.is_word)

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

Using a trie to prune a search

In Word Search II, searching for each word separately repeats work. Insert all words into a trie, then DFS the grid once, following trie children. As soon as the current path isn't a prefix of any word, stop exploring. Store the full word at its terminal node so you can record it directly, and remove found words to avoid duplicates.

Autocomplete

For "top suggestions for a prefix", walk to the prefix node, then collect words beneath it. In production systems (see the autocomplete design question), each node caches its top-K completions so lookups don't traverse the subtree.

Complexity

Insert / search: O(L)
Space: O(total characters) in the worst case — tries trade memory for speed

[!TIP] Practice Word Search II · Word Break