A tree where each edge is one character. Words that share a prefix share a path. Insert and search cost O(L) for a word of length L, no matter how many words are stored.
A hash set answers “is this exact word here?” in O(L). It cannot answer “does any word start with app?” without scanning every word. A trie answers both with the same short walk. That one extra question, prefix lookup, is why the structure exists.
set is simpler.. that matches any one letter. The trie lets you branch only where words actually exist.Insert app, apple and bat. The path a → p → p is stored once and used by both app and apple:
a → p → p (end: “app”) → l → e (end: “apple”)b → a → t (end: “bat”)The end flag is what tells app (a word) apart from ap (only a prefix). Both nodes exist. Only one is flagged.
Reading the figure. Each circle is one node, and the path from the root spells its prefix. The amber edges are the a → p → p path that both app and apple use. Green ringed nodes have is_end set. Notice the first p: the prefix ap exists but is not a word.
class TrieNode:
"""One node per prefix. Words that share a prefix share nodes."""
def __init__(self) -> None:
# children: next letter -> child node. A dict, so any alphabet works.
self.children: dict[str, TrieNode] = {}
# is_end: True when an inserted word stops exactly here.
# "app" and "apple" share nodes, so this flag tells them apart.
self.is_end = False
def insert_word(root: TrieNode, word: str) -> None:
"""Add word to the trie in O(len(word))."""
node = root
# ch is the next letter of word.
# Invariant: node is the end of the path spelling the letters before ch.
for ch in word:
# No child for ch yet: create it. Later words with this prefix reuse it.
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch] # step down one letter
node.is_end = True # flag the last node: a word stops here
def walk_prefix(root: TrieNode, prefix: str) -> TrieNode | None:
"""Node at the end of prefix, or None if no word starts with it."""
node = root
# Invariant: node spells the letters of prefix read so far.
for ch in prefix:
# Missing child: no stored word continues this way. Stop at once.
if ch not in node.children:
return None
node = node.children[ch] # step down one letter
return node
Reading the figure. Blue nodes already existed, so the walk just steps down. The amber node is new, made because t had no child yet. Green rings mark is_end. The amber arrows are the path the loop walks.
Every trie question is built from these two walks. search(word) is walk_prefix plus a check of is_end. starts_with(prefix) is walk_prefix plus a check for None.
def trie_guided_dfs(node: TrieNode, position) -> None:
"""Explore something else, moving down the trie one letter per step."""
# letter_at(position): the letter this step reads.
# Word Search II: board[r][c]. Wildcard search: word[i].
ch = letter_at(position)
# Prune: no stored word continues with ch, so nothing below can match.
if ch not in node.children:
return
child = node.children[ch] # the trie moves down in step with the search
# A word ends here: report it.
# record(child): Word Search II adds the word stored on child.
if child.is_end:
record(child)
# next_positions(position): where the search may go next.
# Word Search II: the 4 neighbour cells. Wildcard: the next index, i + 1.
for nxt in next_positions(position):
trie_guided_dfs(child, nxt)
Reading the figure. The trie holds cat, car and dog. Green arrows are a search that matches, letter by letter, and ends on a flagged node. Red dashed nodes are letters with no child in the trie. The search returns right there, so it never explores anything below them.
The trie is a pruning oracle. The search only goes where some word still could match. Without it, Word Search II tries every path in the grid once per word.
search("app") returns True after inserting only apple. The flag is the difference between a word and a prefix.Build a class with three methods. insert(word) stores a word. search(word) returns whether that exact word was stored. starts_with(prefix) returns whether any stored word begins with prefix.
search and starts_with share one helper that walks a string and returns the node, or None.search also needs the end flag on the last node.class CharNode:
"""A trie node: children by letter, plus an end-of-word flag."""
def __init__(self) -> None:
# children: next letter -> child node.
self.children: dict[str, CharNode] = {}
# is_end: True when a stored word stops at this node.
self.is_end = False
class Trie:
"""Prefix tree with insert, exact search and prefix search.
Each method costs O(L) for a string of length L.
Example:
>>> trie = Trie()
>>> trie.insert("apple")
>>> trie.search("apple")
True
>>> trie.search("app")
False
>>> trie.starts_with("app")
True
>>> trie.insert("app")
>>> trie.search("app")
True
"""
def __init__(self) -> None:
# The root holds no letter. It stands for the empty prefix "".
self.root = CharNode()
def insert(self, word: str) -> None:
"""Store word.
Args:
word: The word to add.
"""
node = self.root
# Invariant: node spells the letters of word read so far.
for ch in word:
# Create the child on first use. Shared prefixes reuse it later.
if ch not in node.children:
node.children[ch] = CharNode()
node = node.children[ch] # step down one letter
node.is_end = True # a word stops here
def _find(self, text: str) -> CharNode | None:
"""Node reached by spelling text from the root, or None."""
node = self.root
# Invariant: node spells the letters of text read so far.
for ch in text:
# Missing child: no stored word has this prefix.
if ch not in node.children:
return None
node = node.children[ch] # step down one letter
return node
def search(self, word: str) -> bool:
"""Whether word itself was inserted.
Args:
word: The exact word to look for.
Returns:
True only if word was stored, not just a longer word starting with it.
"""
node = self._find(word)
# The path must exist AND end on a flagged node.
return node is not None and node.is_end
def starts_with(self, prefix: str) -> bool:
"""Whether any stored word begins with prefix.
Args:
prefix: The prefix to look for.
Returns:
True if the path for prefix exists.
"""
# The path existing is enough. No end flag needed.
return self._find(prefix) is not None
insert("apple"): creates 5 nodes, a p p l e. Flags the e node.search("app"): walks a p p. The node exists but is not flagged. False.starts_with("app"): same walk, the node exists. True.insert("app"): walks the 3 existing nodes, creates nothing, flags the second p.search("app"): now flagged. True.Reading the figure. Each column is the same trie at a later moment. Amber nodes are the path the call walks. Green ringed nodes have is_end set. In the middle column the walk succeeds but the last node has no flag, so search says no. On the right, insert("app") creates nothing and only sets the flag.
insert("") flags the root. starts_with("") is always True. Ask whether empty words can occur.Build a class with add_word(word) and search(word). The search pattern may contain ., which matches any single letter. Return whether any added word matches the whole pattern.
., try every child. That turns the walk into a DFS. Return True as soon as one branch matches.class WildNode:
"""A trie node for wildcard search."""
def __init__(self) -> None:
# children: next letter -> child node.
self.children: dict[str, WildNode] = {}
# is_end: True when an added word stops at this node.
self.is_end = False
class WordDictionary:
"""Word store whose search treats '.' as any single letter.
Example:
>>> words = WordDictionary()
>>> for w in ["bad", "dad", "mad"]:
... words.add_word(w)
>>> words.search("pad")
False
>>> words.search("bad")
True
>>> words.search(".ad")
True
>>> words.search("b..")
True
>>> words.search("b.")
False
"""
def __init__(self) -> None:
# The root stands for the empty prefix "".
self.root = WildNode()
def add_word(self, word: str) -> None:
"""Store word.
Args:
word: Letters only, no wildcards.
"""
node = self.root
# Invariant: node spells the letters of word read so far.
for ch in word:
# Create the child on first use.
if ch not in node.children:
node.children[ch] = WildNode()
node = node.children[ch] # step down one letter
node.is_end = True # a word stops here
def search(self, pattern: str) -> bool:
"""Whether some stored word matches pattern in full.
Args:
pattern: Letters and '.', where '.' matches any one letter.
Returns:
True if at least one stored word matches.
"""
def match(node: WildNode, i: int) -> bool:
"""Can the subtree under node match pattern[i:]?"""
# i == len(pattern): every symbol matched. A word must end here.
if i == len(pattern):
return node.is_end
ch = pattern[i]
if ch == ".":
# '.': any one letter, so try every child.
# i + 1: the next symbol. any() stops at the first True.
return any(match(child, i + 1) for child in node.children.values())
# A plain letter: only one child can match it.
child = node.children.get(ch)
# i + 1: move on to the next symbol of the pattern.
return child is not None and match(child, i + 1)
# 0: start matching at the first symbol, from the root.
return match(self.root, 0)
Stored: bad, dad, mad. Search .ad:
.. Try children b, d, m in turn.b: symbol 1 a exists. Symbol 2 d exists.i == 3, the end of the pattern. The d node is flagged. True, and any stops without trying d or m.b. reaches the end at the a node, which is not flagged. False.Reading the figure. The violet letters on top are the pattern, one column per symbol. The dot could follow b, d or m. Green is the branch that was tried and matched to a flagged node. Grey dashed branches were never visited, because any returned on the first True.
...: matches any stored word of length 3.False.Given a grid of letters and a list of words, return every word that can be spelled by a path of adjacent cells (up, down, left, right). A path may not use the same cell twice.
class GridNode:
"""A trie node that stores the whole word at its end."""
def __init__(self) -> None:
# children: next letter -> child node.
self.children: dict[str, GridNode] = {}
# word: the full word ending here, or None if no word ends here.
# Storing the word, not a flag, means DFS never rebuilds the string.
self.word: str | None = None
def find_words(board: list[list[str]], words: list[str]) -> list[str]:
"""Every word from words that can be traced on the board.
Args:
board: Grid of single letters. It is changed during the search and
restored before returning.
words: Candidate words.
Returns:
The words found, sorted, each listed once.
Example:
>>> grid = [["o", "a", "a", "n"],
... ["e", "t", "a", "e"],
... ["i", "h", "k", "r"],
... ["i", "f", "l", "v"]]
>>> find_words(grid, ["oath", "pea", "eat", "rain"])
['eat', 'oath']
"""
# Empty grid, or a grid with empty rows: nothing can be spelled.
# board[0]: the first row, used to read the column count below.
if not board or not board[0]:
return []
# Build one trie holding every word.
root = GridNode()
for word in words:
node = root
# Invariant: node spells the letters of word read so far.
for ch in word:
if ch not in node.children:
node.children[ch] = GridNode()
node = node.children[ch] # step down one letter
node.word = word # the end node remembers the word
# board[0]: every row has the same length, so row 0 gives the width.
rows, cols = len(board), len(board[0])
found: list[str] = []
def dfs(r: int, c: int, parent: GridNode) -> None:
"""Extend the path into cell (r, c), one level below parent."""
ch = board[r][c]
node = parent.children.get(ch)
# No child: no word has this prefix. Also catches "#", a used cell.
if node is None:
return
# A word ends here. Report it, then clear it so it is reported once.
if node.word is not None:
found.append(node.word)
node.word = None # None: this word is done
board[r][c] = "#" # "#": mark used, no word contains it
# The 4 neighbours: down, up, right, left. 1 and -1 are one step.
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
# 0 <= ... < rows/cols: stay inside the grid.
if 0 <= nr < rows and 0 <= nc < cols:
dfs(nr, nc, node)
board[r][c] = ch # backtrack: give the cell back
# Prune: a leaf with no word left can never match again. Cut it off
# so later starts do not walk into it.
if not node.children and node.word is None:
del parent.children[ch]
# Try every cell as the first letter.
# Invariant: found holds every word that starts at a cell already tried.
for r in range(rows):
for c in range(cols):
dfs(r, c, root)
return sorted(found)
Words oath, pea, eat, rain on the grid in the example:
o, p, e, r.o. The DFS follows o → a → t → h through (0, 1), (1, 1), (2, 1). It finds oath, clears it, and prunes the now empty h leaf, then t, a, o on the way back.a. No root child a, so it stops in one step. Most cells end this way.e. The DFS follows e → a → t through (1, 2), (1, 1). It finds eat.pea has no p on the grid. rain has r at (2, 3) but no a next to it. Result: ['eat', 'oath'].Reading the figure. On the left, green cells and arrows trace oath. Violet traces eat, which reuses the same t cell. On the right is the trie of all four words. Ringed nodes are words found. Dashed nodes are never reached, because the grid has no next letter to match. Every other start cell fails at the root in one step.
L is the longest word. The first step has 4 directions, then 3, since you never step back onto the cell you came from. Pruning makes real runs far faster than this bound.
eat and eats: the first is reported and the DFS keeps going for the second. The node is only pruned when it has no children left."#" is safe: no word contains it, so parent.children.get("#") is always None. Ask if the alphabet could include it.Given a dictionary of roots and a sentence, replace every word with the shortest root that is a prefix of it. Words with no matching root stay as they are.
class RootNode:
"""A trie node for dictionary roots."""
def __init__(self) -> None:
# children: next letter -> child node.
self.children: dict[str, RootNode] = {}
# is_end: True when a root stops at this node.
self.is_end = False
def replace_words(dictionary: list[str], sentence: str) -> str:
"""Replace each word with the shortest dictionary root it starts with.
Args:
dictionary: Root words.
sentence: Words separated by single spaces.
Returns:
The sentence with every word replaced by its shortest root, if any.
Example:
>>> replace_words(["cat", "bat", "rat"], "the cattle was rattled")
'the cat was rat'
>>> replace_words(["a", "aa"], "aadsfasf absbs bbab")
'a a bbab'
"""
# Build the trie of roots.
root = RootNode()
for stem in dictionary:
node = root
# Invariant: node spells the letters of stem read so far.
for ch in stem:
if ch not in node.children:
node.children[ch] = RootNode()
node = node.children[ch] # step down one letter
node.is_end = True # a root stops here
def shortest_root(word: str) -> str:
"""The shortest root that prefixes word, or word itself."""
node = root
# i is the index of ch in word.
# Invariant: no root is a prefix of word[:i], or we would have returned.
for i, ch in enumerate(word):
# No child: no root continues this way. Keep the word.
if ch not in node.children:
return word
node = node.children[ch] # step down one letter
# First flagged node on the walk: the shortest matching root.
if node.is_end:
return word[:i + 1] # + 1: slice end is exclusive, keep ch
# The word ran out first: it is a prefix of a root, not the reverse.
return word
# split() then " ".join: rebuild the sentence one word at a time.
return " ".join(shortest_root(word) for word in sentence.split())
Roots cat, bat, rat. Sentence the cattle was rattled:
the: root has no t child. Kept.cattle: walks c a t. The t node is flagged after 3 letters, so return word[:3], which is cat.was: no w child. Kept.rattled: walks r a t, flagged. Becomes rat.Reading the figure. The trie holds the roots. Amber nodes are the paths that cattle and rattled walk. Each walk stops at the first green ringed node, so the rest of the word is never read. On the right, green results were replaced. Grey ones had no matching first letter and stay as they are.
a and aa: the walk stops at the first flag, so the shorter root wins.split() drops them, so the output has single spaces. Ask if spacing must be kept.A trie splits strings letter by letter. Pattern 19, Bit Manipulation, splits numbers bit by bit. The two meet in Maximum XOR of Two Numbers, which stores each number in a trie of its bits.