Trie Pattern: Template + 49 LeetCode Problems

What the trie pattern is

A trie stores a set of strings as a tree in which each edge is one character and each path from the root spells a prefix, so words sharing a prefix share the nodes that spell it. Lookup and insertion cost the length of the word and nothing else — the size of the dictionary does not appear in the complexity, which is why a trie beats a hash set for every question about prefixes rather than whole words. The node needs exactly two things: a map from character to child, and a flag saying a word ends here, because "car" being present must be distinguishable from "car" merely being a prefix of "cart". Two extensions cover most of the harder problems: storing a count or the best word at each node answers autocomplete queries without walking the subtree, and pairing a trie with a backtracking search over a grid prunes whole regions the moment the prefix stops existing, which is what makes a word-search-over-a-dictionary tractable.

When to use it

• —Queries are about prefixes: autocomplete, "does any word start with…", longest common prefix.
• —A large dictionary is searched many times and repeated prefix work is the bottleneck.
• —A backtracking search over a grid or a string needs to be pruned by a word list.
• —Wildcards must be matched inside words, where a hash set cannot help at all.

The trie template in Python

The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 49 problems listed below.

class Trie:
    def __init__(self):
        self.children = {}
        self.is_word = False       # "car" present vs. "car" merely a prefix of "cart"

    def insert(self, word):
        node = self
        for char in word:
            node = node.children.setdefault(char, Trie())
        node.is_word = True

    def find(self, prefix):
        """The node reached by prefix, or None. is_word tells you if it is a word."""
        node = self
        for char in prefix:
            node = node.children.get(char)
            if node is None:
                return None
        return node

Complexity characteristics

Time

O(L) per insert or lookup, where L is the length of the word

Auxiliary space

O(total characters stored)

The cost of a lookup is the length of the key and nothing else — the number of words already stored does not appear in it, which is the property a hash set cannot match for prefix queries. The space is one node per distinct prefix, so a dictionary with heavy prefix sharing costs far less than the sum of its word lengths and one with none costs exactly that sum. Pairing a trie with a grid search prunes the moment a prefix stops existing, which changes the observed cost by orders of magnitude without changing the worst case.

All 49 trie LeetCode problems

Every problem in the library the trie pattern applies to, grouped by LeetCode's own difficulty rating. 36 of the 49 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.

Related patterns

Problems sit in more than one pattern more often than not, and the overlap is where the interesting follow-up questions live.

Trie pattern FAQ

More ways in: all 22 patterns, the curated study lists, or the full problem list.