Pattern 25 of 27

Trie

Store strings character by character in a shared tree so a prefix lookup costs the prefix length, not the number of words.

Cost: O(L) per insert or lookup, where L is the word length
Problems: 6

When to reach for it

The prompt mentions prefixes, autocomplete, or many words searched together.
Many words have to be matched against the same text or grid.
Hashing whole words cannot answer questions about prefixes.

How it works

A trie turns a word list into a tree where each edge is a character and a marker flags the end of a complete word. Words that share a prefix share nodes, so checking whether any word starts with a prefix is one walk down the tree. A wildcard in a search branches into every child, and Word Search II walks the trie and the grid together, abandoning a path the moment the trie has no child for the next letter.

The template

Written for Implement Trie (Prefix Tree) (write-up)

class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node["$"] = True              # marks the end of a whole word

    def _walk(self, s):
        node = self.root
        for ch in s:
            if ch not in node:
                return None
            node = node[ch]
        return node

    def search(self, word):
        node = self._walk(word)
        return node is not None and "$" in node

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

Open in the editor Trace it line by line

Six problems, in learning order

1.Implement Trie (Prefix Tree)LeetCode 208Nested dictionaries with an end-of-word marker.Medium
2.Design Add and Search Words Data StructureLeetCode 211A dot branches into every child during search.Medium
3.Word Search IILeetCode 212DFS the grid while walking the trie, pruning when no child exists.Hard
4.Replace WordsLeetCode 648Replace each word with the shortest root found while walking it.Not in the curated 370 yet.Medium
5.Map Sum PairsLeetCode 677Store a running sum at every node along each inserted key.Not in the curated 370 yet.Medium
6.Search Suggestions SystemLeetCode 1268Walk the typed prefix and collect up to three words in sorted order.Not in the curated 370 yet.Medium

What usually goes wrong

Confusing search, which needs a whole word, with startsWith, which accepts any prefix.
Not removing words already found in Word Search II, which returns duplicates and wastes time.
Allocating a 26-slot array per node in Python when a dictionary is lighter.

Trie, answered

When should I use the trie pattern?

The prompt mentions prefixes, autocomplete, or many words searched together. Many words have to be matched against the same text or grid. Hashing whole words cannot answer questions about prefixes.

What is the time complexity of trie?

O(L) per insert or lookup, where L is the word length. A wildcard in a search branches into every child, and Word Search II walks the trie and the grid together, abandoning a path the moment the trie has no child for the next letter.

Which problem should I start with for trie?

Start with Implement Trie (Prefix Tree) (LeetCode 208, Medium). Nested dictionaries with an end-of-word marker. The six problems on this page are in learning order.