Tries
A search box that completes a word as we type it keeps a list of words and has to answer one kind of question over and over: which of the words begin with the letters typed so far. A prefix of a word is a run of letters at its start, so m, ma and map itself are prefixes of map. A trie is a tree that stores a set of words in such a way that finding whether any stored word begins with a prefix takes one step for each letter of the prefix, however many words are stored. The first problem asks us to build one.
Write a class Trie that stores words made of lowercase letters. insert(word) adds a word. search(word) returns whether exactly this word has been inserted. startsWith(prefix) returns whether some inserted word begins with prefix.
The input lists the calls in order. The output lists what each call returns, with null for the constructor and for insert.
Constraints
- Words and prefixes have 1 to 2000 lowercase letters
- At most calls in total
Sample · Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]
In the sample, apple is inserted first. search("app") is then false, because app itself was never inserted, and startsWith("app") is true, because apple begins with app. Once app has been inserted too, search("app") is true.
The simplest way to store the words is a list. insert appends the word, and each of the two questions compares its argument with every word in the list. The problem allows 30,000 calls. Suppose the first 15,000 insert a word each and the other 15,000 ask a question:
Even if every comparison stopped at its first letter, this would be slow in Python: a loop of 225 million startswith calls that each failed at the first letter took about 6 seconds when we ran it. A comparison reads letters until the two strings differ, and for long words that begin alike that can be close to 2,000 letters, the longest word the problem allows.
A hash set handles search: it finds a word in time proportional to the word's length, however many words it holds. It does not help with startsWith: the set can say whether app is one of its entries, but it has no way to find the longer entries that begin with app. A second set that held every prefix of every inserted word would make startsWith one lookup as well, but a word of 2,000 letters has 2,000 prefixes, and stored as strings of their own they take letters.
A trie holds the same prefixes, but it stores each one as a single letter added to a shorter prefix.
The structure of a trie
Take the three words map, mat and sun. Three words of three letters have nine prefixes between them, but only seven of these are different, because map and mat both have the prefixes m and ma. The seven are m, ma, map, mat, s, su and sun.
The trie for these words is a rooted tree. Its root stands for the empty string, and below the root it has one node for each of the seven prefixes. We name a node by its prefix. Every node below the root is a child of the node whose prefix is one letter shorter, and the edge between the two is labelled with the letter that was added. The node ma, for example, is a child of the node m, and the edge from m to ma is labelled a.
map, mat and sun. A ring marks a node where a stored word ends. The two highlighted edges are the walk for the prefix ma, and the dashed region holds the nodes whose prefixes begin with ma.Reading the edge labels on the way down from the root to a node spells the prefix of that node: m, a and then p spells map.
The node ma is in the trie although ma is not one of the three words. To tell the words from the other prefixes, a node carries an end mark when a stored word ends at it. In the figure the marked nodes have a ring: map, mat and sun. We cannot treat the nodes without children, the leaves, as the words instead, because a word can be a prefix of another word. If maps were stored as well, the node map would have a child and would still be a word.
To insert a word, we start at the root and take the letters of the word one at a time. If the node we are at has an edge for the letter, we follow it. If it has none, we create a child for that letter and move to it. The node we are at after the last letter gets the end mark. Starting from a trie that is only a root, the three words go in like this:
map: the root has no edges yet, so every letter creates a node: m, ma and map. The node map gets the end mark.mat: the edges for m and a exist, so we follow them to the node ma. It has no edge for t, so we create the node mat and mark it.sun: the root has no edge for s, so we create s, su and sun, and mark sun.
The two questions of the problem are the same walk with nothing created. For startsWith("ma") we follow the edge m and then the edge a from the root, the two edges highlighted in the figure. Both exist, so some stored word begins with ma. For search("ma") we make the same walk and then look at the node it ends on, which has no end mark, so the answer is false. A walk for mo stops at the node m, which has no edge for o. A stored word that began with mo would have created that edge, so there is no such word, and both questions are answered false.
Insert and search in code
In Python, a node is an object with two fields. children is a dictionary that maps a letter to the child for that letter, so the node has an edge for a letter exactly when the letter is a key. end is the end mark.
class Node:
def __init__(self):
self.children = {} # letter -> the child node for that letter
self.end = False # True when a stored word ends here
class Trie:
def __init__(self):
self.root = Node()
def insert(self, word):
node = self.root
for letter in word:
if letter not in node.children:
node.children[letter] = Node()
node = node.children[letter]
node.end = True
def find(self, prefix): # the node that spells prefix, or None
node = self.root
for letter in prefix:
if letter not in node.children:
return None
node = node.children[letter]
return node
def search(self, word):
node = self.find(word)
return node is not None and node.end
def startsWith(self, prefix):
return self.find(prefix) is not None
trie = Trie()
trie.insert("apple")
print(trie.search("apple"), trie.search("app"), trie.startsWith("app"))
trie.insert("app")
print(trie.search("app"))The lines after the class replay the sample.
find is the walk that both questions share. It returns the node that spells its argument, or None when the walk comes to a missing edge. search then looks at the end mark of the node, and startsWith only needs the node to exist.
Inserting a word a second time follows nodes that all exist and sets a mark that is already set, so the trie does not change.
Time and memory of a trie
- `insert`, `search`, `startsWith`
- Each method takes one step for each letter of its argument, a word of letters. It does not depend on how many words are stored.
- Number of nodes
at most total letters - Inserting a word creates at most one node for each of its letters, and fewer when it shares a prefix with a word that is already stored. The 1 is the root.
So the 30,000 calls of the problem take at most steps, where the list needed 225,000,000 comparisons of strings, each of which can read up to 2,000 letters.
A trie takes much more memory than the words it stores, because every node is an object with a dictionary of its own. We built the trie for 100,000 random words of 8 letters, which are 800,000 letters in all. It had 507,569 nodes and took 127 MB on Python 3.14, about 250 bytes for each node.
So when every question is about a whole word, a hash set is the better choice: it answers in the same time with less code and less memory. A trie is the structure to use when the questions are about prefixes, or have to be answered one letter at a time, as in the rest of this lesson.
A trie to try the operations on
The widget starts from the trie for map, mat and sun, with the prefix ma looked up. It writes on each node only the letter of the edge that leads to it. Add maps: the widget reports that three letters followed nodes that already existed and one letter created a new node, and the node where map ends keeps its ring although it now has a child.
Removing a word undoes its insert. It clears the word's end mark, then walks back up the word's path and deletes each node that has no children and no end mark. It stops at the first node that still has a child or an end mark, because another stored word passes through that node or ends there. Remove map: only its ring goes, because maps still passes through its nodes. Look up the prefixes mo and s, and then the empty prefix, for which the walk stays at the root and every stored word matches.
The Show prefix counts switch writes on every node the number of stored words that pass through it. A later part of this page uses these counts.
Deeper read: other ways to store the children of a node
Two ways to store the children of a node are an array with one slot for each symbol of the alphabet, and a map from a symbol to a child, which is a dictionary in Python and a map in C++. The array finds a child by position and keeps the children in alphabetical order, but it spends a slot on every symbol in every node, so it suits a small fixed alphabet such as the 26 lowercase letters. The map stores only the edges that exist, so it suits a large alphabet, or one that is not known in advance.
A trie whose words share few prefixes has long chains of nodes with one child each. A radix tree merges each chain into a single edge labelled with a string, which removes most of the nodes.
The words under a prefix
startsWith says whether some stored word begins with a prefix, and the trie can also say which words do. In the figure of the trie for map, mat and sun, the dashed region is the subtree of the node ma: the node itself and everything below it. The nodes in it are exactly the nodes whose prefixes begin with ma, and the marked ones, map and mat, are the stored words that begin with ma. So to list the words with a given prefix, we walk to the node of the prefix and visit its subtree. Search Suggestions System asks for such a list after every typed letter.
You get a list of product names, all different, and a search word, all in lowercase letters. After each letter of the search word is typed, suggest the products that begin with the letters typed so far: all of them when there are at most three, and the three that come first in alphabetical order when there are more.
Return one list of suggestions for each typed letter.
Constraints
-
products.length - Each product has 1 to 3000 letters, and all products together have at most letters
- The search word has 1 to 1000 letters
Sample · Input
products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output
[["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]
All five products of the sample begin with m, and all five begin with mo, so the first two lists hold the three products that come first in alphabetical order: mobile, moneypot and monitor. Only mouse and mousepad begin with mou, and they are still the answer after mous and mouse.
We insert the products into a trie and follow the search word down the trie while it is typed. We start at the root, and each typed letter takes us one edge down, so after letters we are at the node of the first letters. If the edge for a typed letter is missing, no product begins with the letters typed so far, and none will after more letters are typed, so every list from there on is empty.
The suggestions come from a walk of the subtree of that node. At each node the walk first records the node's word, if the node has an end mark, and then visits the children in alphabetical order of their letters. A walk that handles a node before its children is called a preorder walk.
This walk meets the stored words in alphabetical order, for two reasons. A word is recorded before every longer word that begins with it, as mouse is before mousepad. And when two words first differ at some letter, their paths split at the node above that letter, and the walk finishes the branch with the smaller letter before it starts the other. For moneypot and monitor the paths split at the node mon, and the walk records moneypot, under the edge e, before it reaches the edge i. Once the walk has three words, every further call returns at once.
sys.setrecursionlimit(5000) # a product of 3,000 letters nests 3,000 calls of collect
class Node:
def __init__(self):
self.children = {}
self.end = False
def insert(root, word):
node = root
for letter in word:
if letter not in node.children:
node.children[letter] = Node()
node = node.children[letter]
node.end = True
def collect(node, prefix, found): # the words under node, smallest first, until found has 3
if len(found) == 3:
return
if node.end:
found.append(prefix)
for letter in sorted(node.children):
collect(node.children[letter], prefix + letter, found)
def suggested_products(products, search_word):
root = Node()
for product in products:
insert(root, product)
answer = []
node = root
for i, letter in enumerate(search_word):
if node is not None:
node = node.children.get(letter) # one step down, or None
found = []
if node is not None:
collect(node, search_word[:i + 1], found)
answer.append(found)
return answer
products = ["mobile", "mouse", "moneypot", "monitor", "mousepad"]
for row in suggested_products(products, "mouse"):
print(*row)sorted(node.children) gives the letters of the edges in alphabetical order. Without it the loop would take them in the order they were inserted, which is the order a dictionary keeps, and the first list of the sample would be mobile, mouse and mousepad. collect nests one call for each letter of a word, and a product can have 3,000 letters, so the first lines of the program raise the limit of about 1,000 nested calls that Python sets by default.
Each call also builds prefix + letter as a new string, which copies the prefix. When the typed letters match the start of a product of 3,000 letters, each keystroke copies up to about million letters, and 1,000 keystrokes copy about 4.3 billion. That took about half a second when we ran it, so the program keeps the simpler code.
Building the trie reads every product letter once, which is at most steps. A keystroke then costs one step down and a walk that ends at the third word. Only inserting a word creates nodes, so every node has a stored word at it or below it. So the walk never goes down a branch without a word, and the nodes it visits before it has three words all lie on the paths to those three words: at most nodes, however many products there are.
Deeper read: the same suggestions without a trie
At the limits of this problem a plain scan passes too: comparing every product with the typed letters after each of 1,000 keystrokes reads at most letters. The scan takes longer as the list of products grows, but the walk in the trie does not take longer.
A sorted list does better than the scan. In it, the products that begin with a prefix sit together in one block. Any word that falls between two words beginning with mo in alphabetical order begins with mo too, and the same holds for every prefix. The block starts at the first product that is not smaller than the prefix. A binary search finds that product, and the suggestions are it and the two after it, as long as they still begin with the prefix. Sorting takes comparisons, and each keystroke takes one binary search.
This is less code than the trie, and it is enough when the list of words does not change. A trie does better when words arrive between the questions: inserting into a sorted list moves every word behind the new one, and inserting into a trie touches only the nodes of the new word.
A count on every node
Listing the words under a prefix has to visit them. To count them without the visit, every node can store the number of stored words that begin with its prefix. A word begins with the prefix of a node exactly when inserting the word passed through that node, so insert keeps the numbers right by adding 1 to every node it moves to. In the trie for map, mat and sun, the nodes m and ma have the count 2 and the other five nodes have the count 1. Sum of Prefix Scores of Strings asks for sums of such counts.
You get a list of words. The score of a string is the number of words in the list that have it as a prefix, where a word counts as a prefix of itself. For each word, return the sum of the scores of all its non-empty prefixes.
Constraints
- Each word has 1 to 1000 lowercase letters
Sample · Input
words = ["abc","ab","bc","b"]
Output
[5,4,3,2]
In the sample, the word abc has the prefixes a, ab and abc. Two words of the list begin with a, namely abc and ab. The same two begin with ab, and only abc begins with abc. So the answer for abc is .
Computed directly, the score of one prefix takes a comparison with every word of the list, and a word has up to 1,000 prefixes:
With a count on every node, the score of a prefix is the count of its node. We insert all the words, and then walk each word down the trie a second time and add up the counts of the nodes it passes.
abc passes the counts 2, 2 and 1.class Node:
def __init__(self):
self.children = {}
self.count = 0 # stored words that begin with this node's prefix
def sum_prefix_scores(words):
root = Node()
for word in words:
node = root
for letter in word:
if letter not in node.children:
node.children[letter] = Node()
node = node.children[letter]
node.count += 1 # one more word passes through this node
answer = []
for word in words:
node = root
score = 0
for letter in word:
node = node.children[letter]
score += node.count # the score of this prefix
answer.append(score)
return answer
print(*sum_prefix_scores(["abc", "ab", "bc", "b"]))The listing leaves out the end marks that the figure draws, because the problem never asks whether a string is one of the words. A word that is in the list twice is inserted twice and counted twice, as the score requires. Both passes read every letter of every word once:
Search with a wildcard
In every walk so far, each letter of the word we looked up named one edge to follow. Design Add and Search Words lets the searched word leave a letter open, as a dot that matches any letter.
Write a class WordDictionary. addWord(word) stores a word of lowercase letters. search(word) returns whether some stored word matches word, which may contain dots. A dot matches any one letter, and every other character must be equal to the letter in its place.
Constraints
- Words have 1 to 25 characters
- A searched word contains at most 2 dots
- At most calls to
addWordandsearchin total
Sample · Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"] [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]
The sample stores bad, dad and mad. pad is not found, because no stored word begins with p. .ad matches all three words, and b.. matches bad.
addWord is the trie's insert, unchanged. search walks down as before as long as the characters are letters. At a dot there is no single edge to follow, because any edge may be the one that leads to a match. So the search tries every child of the node it is at: it searches for the rest of the word below each child in turn, and it succeeds as soon as one of those searches does.
This makes the walk a recursive function of two things, the node it is at and the position it has reached in the word. When the word is used up, the answer is the end mark of the node the search is at.
For .ad in the sample, the root has the children b, d and m. The search goes to b first, follows the edge a and then the edge d, finds an end mark on the node bad, and returns true without trying d or m.
class Node:
def __init__(self):
self.children = {}
self.end = False
class WordDictionary:
def __init__(self):
self.root = Node()
def addWord(self, word):
node = self.root
for letter in word:
if letter not in node.children:
node.children[letter] = Node()
node = node.children[letter]
node.end = True
def search(self, word):
def match(node, i): # does word[i:] match some path below node?
if i == len(word):
return node.end
if word[i] == ".": # any letter: try every child
for child in node.children.values():
if match(child, i + 1):
return True
return False
child = node.children.get(word[i])
return child is not None and match(child, i + 1)
return match(self.root, 0)
d = WordDictionary()
for word in ["bad", "dad", "mad"]:
d.addWord(word)
print(d.search("pad"), d.search("bad"), d.search(".ad"), d.search("b.."))The last lines replay the sample.
A word without dots still follows one path. Each dot can multiply the number of paths by up to 26, the number of children a node can have, but the search follows only the edges that exist. With at most 2 dots and 25 characters, one search in the trie visits at most
A hash set has no edges to follow. It would have to look up every way of filling in the dots, which is always words for two dots, and each lookup reads the whole word, up to 25 letters. That is about the same 16,900 letters on every such search, while the trie reaches its bound only when the stored words use every branch the dots allow.
Search a grid for many words
Word Search II looks for many words at once in a grid of letters, and a trie tells the search which paths are worth continuing.
You get a grid of lowercase letters and a list of words, all different. A word is on the board when a path of cells spells it, where each cell of the path is next to the one before it, horizontally or vertically, and no cell is used twice. Return every word of the list that is on the board, in any order.
Constraints
- The grid has 1 to 12 rows and 1 to 12 columns
- 1 to words, each of 1 to 10 letters
Sample · Input
board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output
["eat","oath"]
oath.On this board oath starts in the top left corner and goes right, down and down. eat starts at the e that ends the second row and goes left twice. No cell holds a p, so pea is not on the board, and the only r has no a next to it, so rain is not either.
A path on the board is built by backtracking: the search makes one choice at a time, here the next cell, and undoes each choice afterwards. From the last cell of the path, the search tries the four places above, below, left and right of it, leaving out a place that is off the board and a cell that is already on the path. To know which cells are on the path, the search marks a cell when the path takes it and removes the mark when it backs out of the cell, which is the undo step.
Searching for the words one at a time would repeat work, because words that begin with the same letters send the search along the same paths. So we search the grid once, for all the words together. The words go into a trie, and the search starts a path from every cell of the board in turn. The search also keeps the trie node whose prefix is the letters of the path, which is the root while the path is empty. Each time the path tries to take a new cell, the search looks for the edge from that node for the letter of the cell:
- If there is no such edge, no word begins with the letters of the longer path, and the search does not take the cell.
- If there is one, the path takes the cell and the search moves along the edge. When the node it arrives at has an end mark, the path spells a word, and the word goes into the answer. The search then clears the mark, so that a word that several paths spell is reported once.
class Node:
def __init__(self):
self.children = {}
self.end = False
def insert(root, word):
node = root
for letter in word:
if letter not in node.children:
node.children[letter] = Node()
node = node.children[letter]
node.end = True
def find_words(board, words):
root = Node()
for word in words:
insert(root, word)
rows, cols = len(board), len(board[0])
found = []
def visit(r, c, node, path): # node spells the path so far; (r, c) is the cell it tries to take
letter = board[r][c]
if letter not in node.children:
return # no word continues with this letter
node = node.children[letter]
path += letter
if node.end:
found.append(path)
node.end = False # report each word once
board[r][c] = "#" # the cell is on the path
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != "#":
visit(nr, nc, node, path)
board[r][c] = letter # take the cell off the path again
for r in range(rows):
for c in range(cols):
visit(r, c, root, "")
return found
board = [list("oaan"), list("etae"), list("ihkr"), list("iflv")]
print(*sorted(find_words(board, ["oath", "pea", "eat", "rain"])))The words are printed in sorted order to match the sample.
board[r][c] is the letter in row r and column c. A cell on the path is marked by overwriting its letter with #, and the letter is put back when the call ends. path += letter makes a new string that belongs to this call and leaves the caller's string as it was, so the path needs no undoing.
A path is at most 10 cells long, because no node of the trie is deeper than the longest word. It has at most 4 ways to take its second cell and at most 3 ways to take each cell after that, since it cannot go back, so the number of paths from one starting cell is at most
On the largest board, with 144 cells, that is at most million paths, however many words there are, and the trie stops most of them early. On the sample board only four of the sixteen cells hold a letter that some word begins with, and the search from each of the other twelve ends at its first step.
A trie of bits
A trie can store strings of any symbols, and a number written in binary is a string of 0s and 1s. A trie of such strings, in which a node has at most two children, answers questions about XOR.
You get an array nums of non-negative integers. Return the largest value of nums[i] XOR nums[j] over all pairs of positions with .
Constraints
-
nums.length -
nums[i]
Sample · Input
nums = [3,10,5,25,2,8]
Output
28
XOR compares two numbers bit by bit, and a bit of the result is 1 where the two numbers differ. In the sample the answer 28 is 5 XOR 25:
Trying every pair of numbers takes about XORs, which is for numbers.
To do better, we fix one number and look for the number in the array that gives the largest XOR with it. A 1 in a higher bit of the result is worth more than 1s in all the lower bits together:
So if some number differs from in the highest bit, the best partner for is one of those numbers, whatever their lower bits are. Among those numbers, or among all of them if none differs there, the same reasoning applies to the next bit, and so on down to the lowest bit.
Choosing bit by bit from the top is a walk down a trie. We write every number with the same count of bits, with zeros in front where needed, and store the numbers in a trie of bits. The path for a number starts at the root and, for each bit from the highest down, goes to the child for 0 or the child for 1.
For each we then walk down from the root. At every level we take the child for the bit opposite to the bit of if that child exists, and otherwise the child for the same bit. Every step to an opposite bit puts a 1 into the result.
Here is the trie for the sample, drawn on five bits, with the walk for , which is 00101:
11100, which is 28.The values in the problem go up to , so the program stores 31 bits for each number, numbered from 30 down to 0, where bit is the bit worth . In the code, (x >> k) & 1 is bit of x: the shift moves that bit to the last place, and & 1 keeps only the last place. 1 << k is the number whose only 1 is bit , and value |= 1 << k sets that bit of value.
class Node:
def __init__(self):
self.children = {} # 0 or 1 -> the child node for that bit
def find_maximum_xor(nums):
root = Node()
for x in nums: # store x as 31 bits, highest first
node = root
for k in range(30, -1, -1):
bit = (x >> k) & 1
if bit not in node.children:
node.children[bit] = Node()
node = node.children[bit]
best = 0
for x in nums:
node = root
value = 0 # x XOR the number the walk spells
for k in range(30, -1, -1):
bit = (x >> k) & 1
if (1 - bit) in node.children: # a stored number differs from x in bit k
value |= 1 << k
node = node.children[1 - bit]
else:
node = node.children[bit]
best = max(best, value)
return best
print(find_maximum_xor([3, 10, 5, 25, 2, 8]))Every stored number ends at the same depth, 31 edges below the root. So the nodes need no end mark, and the walk always has a child to move to until it has taken its 31 steps. Each number is inserted in 31 steps and looked up in 31 more, against the XORs of trying every pair:
The trie has one Python object for each node, and there can be millions of nodes. For 200,000 random numbers this program made 2.9 million of them and took 2.3 seconds and 880 MB when we ran it. A lighter version numbers the nodes and keeps their children in two lists of integers, one list for each bit. It took 1.1 seconds and 290 MB.
Common mistakes with tries
Answering
searchfrom the walk alone, without looking at the end mark.- Where it breaks
- With only
mapsstored, the walk formapends on a node, sosearch("map")returns true. The answer is false. - The fix
- Return true only when the walk succeeds and the node it ends on has the end mark.
Returning from inside the loop over the children at a dot.
- Where it breaks
- With
abandcdstored,search(".d")tries the child a, finds no d below it and returns false without trying c. The answer is true. - The fix
- Inside the loop, return only when a child matches. Return false after the loop.
Inserting and walking the bits of a number from the lowest bit up.
- Where it breaks
- The walk then chooses the low bits first. On
[3, 10, 5, 25, 2, 8]it returns 27, but the answer is 28. - The fix
- Insert and walk from the highest bit down to bit 0.
Recall A trie holds `map`, `mat` and `sun`. Then `maps` and `sum` are inserted. How many nodes does it have now, which nodes have an end mark, and what do `search("ma")`, `startsWith("su")` and `search("sum")` return?
maps follows the three nodes m, ma and map and creates one node, and sum follows s and su and creates one, so the trie has nodes besides the root, and 10 with it. Five nodes have an end mark: map, maps, mat, sum and sun. search("ma") is false, because the node ma exists and has no mark. startsWith("su") is true, and so is search("sum").
Further reading
- Antti Laaksonen, free PDFCompetitive Programmer’s Handbook, section 26.2: Trie structure(opens in a new tab)
A short section with a drawn trie of four words, the reason for the end mark, counts stored in the nodes, and all the nodes kept in one array
trie[N][A]. - USACO GuideString Searching(opens in a new tab)
Its Tries section solves CSES Word Combinations with a trie and dynamic programming, which our roadmap reaches later, and lists practice problems, many of them on tries of bits.
- OI Wiki, in Chinese字典树 (Trie)(opens in a new tab)
Array-based tries, then the trie of bits for the largest XOR, for XOR sums, and merged and persistent tries.
- cp-algorithmsAho-Corasick algorithm(opens in a new tab)
Starts by building the trie of a set of patterns, then adds links between its nodes so that one pass over a text finds every pattern in it.
- WikipediaRadix tree(opens in a new tab)
A trie in which each chain of nodes with one child is merged into one edge labelled with a string.
- Pat MorinOpen Data Structures, Chapter 13: Data Structures for Integers(opens in a new tab)
Section 13.1 stores -bit integers in a binary trie, each as a path from the root down to depth , and adds, finds and removes a value in steps; a removal walks back up the path and deletes the nodes no other value uses. Later sections speed up the search with hashing. Parts of this page adapt this chapter’s text, licensed CC BY 2.5 Canada (creativecommons.org/licenses/by/2.5/ca), with changed wording, examples and code.