Trie ApplicationsTries in practice

01Why it exists

Reach for it when you see:Many patterns to find in one piece of text at once, a large dictionary of words to search for on a grid or graph, prefix-based pruning, an integer's bits treated as characters (maximum XOR, XOR distance), counting by prefix.

02The core idea

The trie lesson was about sharing prefixes and walking down one character at a time. All three applications here rest on the same idea: once a pile of strings is stacked into one tree, a single traversal handles all of them at once, at a cost that depends on the size of the tree and the length of the input rather than on how many strings there are. The first is searching with a trie in hand — finding every dictionary word in a grid of letters, for instance (Word Search II). Each cell the DFS steps onto moves one level down the trie in lockstep, and the moment the next letter is not a child, the branch is pruned. Without the trie, every word needs its own backtracking search.

The second is Aho–Corasick multi-pattern matching, a generalisation of KMP. Where KMP's pi table tells you how much of the match you can keep after a mismatch, Aho–Corasick computes a fail link fail(v) for every node v of the trie, pointing at the longest proper suffix of v that is also a prefix in the tree. You build the links with a BFS: node v is its parent u plus a character c, so start at fail(u) and look for a c edge, following fail links further up if there is none. The BFS order guarantees that shallower nodes are finished first. You also make v inherit the output of fail(v), because he is a keyword sitting at the end of she, and landing on she must report both. Scanning the text moves down one step per character and jumps back along fail links when it cannot; the total number of jumps back never exceeds the number of steps down, so scanning is O(n + matches reported), with O(total keyword length × alphabet size) or O(total keyword length) to build.

The third is the bit trie: write each integer in binary with a fixed width, insert it high bit first as if it were a string, and every node has just two children, 0 and 1. To find the number that XORs highest with x, walk down from the high bit and prefer the bit opposite to x's, which is correct because a single 1 in a high position outweighs every lower bit put together. Insertion and lookup are both O(B) for a width of B bits, so n numbers cost O(nB) time and space. Storing a count of how many numbers pass through each node also lets you answer "how many XOR to less than k" or "what is the kth smallest".

Common traps: in Word Search II, failing to clear the end marker after finding a word reports it over and over; forgetting to mark and restore the cells you have walked through; not pruning branches that have emptied out, so the same prefix is searched again and again. For Aho–Corasick, building the fail links in DFS order means fail(u) may not be ready when you compute fail(v); forgetting to collect output along the fail links drops short keywords that sit at the tail of longer ones; and a 26-slot array per node blows up memory once the total keyword length grows, so a large alphabet calls for a hash table instead. A bit trie needs a fixed width, the same one for every number, and negative values require you to think through what the top bit means. Where this sits among its neighbours: the basic trie operations are in the Trie lesson, fail links are KMP's prefix function moved onto a tree, Word Search plus trie pruning is Word Search II, and the bit trie pairs with the properties covered in XOR Tricks.

03The algorithm

1. 1Decide what a "character" is: real characters for ordinary strings, a fixed number of bits (high bit first) for integers. Insert every string or number into the trie.
2. 2To find many words on a grid or graph: carry the current trie node through the DFS, prune as soon as the next cell's character is not a child, and when you hit an end marker, take the answer and clear the marker.
3. 3To find many patterns in one text: use a BFS to give every node a fail link fail(v), and merge the output of fail(v) into the output of v.
4. 4Scan the text: for each character, jump back along the fail links until you can move down or you are back at the root, then report every output at the node you land on.
5. 5Maximum XOR over integers: to query x, walk down from the high bit taking the bit opposite to x's whenever that child exists, and the same bit only when it does not. The value you assemble on the way down is the maximum XOR.

04Interactive demo

Aho–Corasick finding he, she, his and hers in the text ushers, all at once. The first phase inserts the four keywords: blue marks the node just created, green marks the end of a keyword. The second phase adds the fail links with a BFS; the yellow dashed arrows are the links that do not point at the root, and each step explains how the search starts from the parent's fail link: sh points to h, his points to s, she points to he — and since he is itself a keyword, reaching she has to report he too — and hers points to s. The third phase scans the text: blue is the current state. Reading e lands on she and reports both she and he; reading r finds no r edge out of she, so the blue dashed arrow jumps to he and then moves down to her; finally s lands on hers. The text was read exactly once and all three keywords were found.

05Code

Python has a dictionary-based Aho–Corasick, Word Search II with trie pruning (that is LeetCode 212), and a bit trie for maximum XOR. C++ has an array-based Aho–Corasick that fills in the missing transitions after building so the automaton is complete and every character costs one table lookup, plus an array-based bit trie.

from collections import deque


class AhoCorasick:
    """Multi-pattern matching: O(total keyword length) to build, O(n + matches) to scan"""

    def __init__(self, words):
        self.goto = [{}]                        # children of each node: char -> node index
        self.fail = [0]
        self.out = [[]]                         # keywords to report when we land on this node
        for w in words:
            node = 0
            for ch in w:
                if ch not in self.goto[node]:
                    self.goto[node][ch] = len(self.goto)
                    self.goto.append({})
                    self.fail.append(0)
                    self.out.append([])
                node = self.goto[node][ch]
            self.out[node].append(w)
        q = deque(self.goto[0].values())        # every depth-1 fail link points at the root
        while q:                                # BFS: a fail link always points to a shallower, finished node
            u = q.popleft()
            for ch, v in self.goto[u].items():
                q.append(v)
                f = self.fail[u]
                while f and ch not in self.goto[f]:
                    f = self.fail[f]
                self.fail[v] = self.goto[f].get(ch, 0)
                self.out[v] = self.out[v] + self.out[self.fail[v]]   # report suffixes that are keywords too

    def search(self, text):
        res, node = [], 0
        for i, ch in enumerate(text):
            while node and ch not in self.goto[node]:
                node = self.fail[node]          # stuck: jump back along the fail links
            node = self.goto[node].get(ch, 0)
            for w in self.out[node]:
                res.append((i - len(w) + 1, w))
        return res


def find_words(board, words):
    """Word Search II: carry the trie node through the DFS and prune as soon as a prefix is missing"""
    root = {}
    for w in words:
        node = root
        for ch in w:
            node = node.setdefault(ch, {})
        node["$"] = w                           # the end marker stores the whole word
    rows, cols = len(board), len(board[0])
    found = []

    def dfs(r, c, parent):
        ch = board[r][c]
        node = parent.get(ch)
        if node is None:                        # no word starts with this prefix
            return
        if "$" in node:
            found.append(node.pop("$"))         # take it and clear it, so it is not reported twice
        board[r][c] = "#"
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != "#":
                dfs(nr, nc, node)
        board[r][c] = ch
        if not node:
            parent.pop(ch)                      # every word under this prefix is found: prune the branch

    for r in range(rows):
        for c in range(cols):
            dfs(r, c, root)
    return sorted(found)


def max_xor_pair(nums, bits=31):
    """Insert each integer's bits, high bit first, as if it were a string; a query takes the opposite bit whenever it can"""
    root, best = {}, 0
    for x in nums:
        node = root
        for b in range(bits - 1, -1, -1):
            node = node.setdefault((x >> b) & 1, {})
        node, cur = root, 0
        for b in range(bits - 1, -1, -1):
            want = 1 - ((x >> b) & 1)
            if want in node:
                cur |= 1 << b
                node = node[want]
            else:
                node = node[1 - want]
        best = max(best, cur)
    return best


if __name__ == "__main__":
    ac = AhoCorasick(["he", "she", "his", "hers"])
    print(ac.search("ushers"))                  # [(1, 'she'), (2, 'he'), (2, 'hers')]
    board = [list("oaan"), list("etae"), list("ihkr"), list("iflv")]
    print(find_words(board, ["oath", "pea", "eat", "rain"]))   # ['eat', 'oath']
    print(max_xor_pair([3, 10, 5, 25, 2, 8]))   # 28: 5 XOR 25

06Practice

• LeetCode 720Longest Word in Dictionary (every prefix must be a word)Medium
• LeetCode 421Maximum XOR of Two Numbers in an Array (bit trie)Medium
• LeetCode 2416Sum of Prefix Scores of Strings (count visits on each node)Hard
• LeetCode 1032Stream of Characters (Aho–Corasick, or build the trie on reversed words)Hard
• LeetCode 1707Maximum XOR With an Element From Array (sort offline, insert into the bit trie as you go)Hard
• LeetCode 745Prefix and Suffix SearchHard