Introduction to Tries
Editorial
Every keystroke asks the same question
Type on a phone and it guesses the word you're in the middle of. After each letter it has to know: does any word in the dictionary start with what's typed so far? The first way anyone writes that is a scan: check every word with startswith. Here it is against a trie, on 10,000 words and 1,000 typed prefixes, the same in every language:
import time
x = 7 # the same words and prefixes in every language
def next_number():
global x
x = x * 48271 % 2147483647
return x
def word(length):
return "".join(chr(ord("a") + next_number() % 26) for _ in range(length))
class Node:
def __init__(self):
self.children = [None] * 26
def has_prefix(root, p):
node = root
for c in p:
node = node.children[ord(c) - ord("a")]
if node is None:
return False
return True
words = [word(4 + next_number() % 7) for _ in range(10000)]
prefixes = [word(2 + next_number() % 4) for _ in range(1000)]
print(len(words), "words,", len(prefixes), "prefixes asked")
start = time.perf_counter()
found_scan = sum(1 for p in prefixes if any(w.startswith(p) for w in words)) # every word, until one starts with p
scan_ms = round((time.perf_counter() - start) * 1000)
start = time.perf_counter()
root, nodes = Node(), 0
for w in words:
node = root
for c in w:
i = ord(c) - ord("a")
if node.children[i] is None: # a prefix no word had before: one new node
node.children[i] = Node()
nodes += 1
node = node.children[i]
build_ms = round((time.perf_counter() - start) * 1000)
start = time.perf_counter()
found_trie = sum(1 for p in prefixes if has_prefix(root, p))
ask_ms = round((time.perf_counter() - start) * 1000)
print("found:", found_scan, "by the scan,", found_trie, "by the trie")
print("letters in the words:", sum(len(w) for w in words), "| trie nodes:", nodes)
print(f"scan: {scan_ms} ms | trie: {build_ms} ms to build, {ask_ms} ms to answer")
# 10000 words, 1000 prefixes asked
# found: 370 by the scan, 370 by the trie
# letters in the words: 69731 | trie nodes: 47955
# scan: 372 ms | trie: 66 ms to build, 1 ms to answerimport java.util.*;
public class Main {
static long x = 7; // the same words and prefixes in every language
static int nextNumber() {
x = x * 48271 % 2147483647;
return (int) x;
}
static String word(int length) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < length; i++) sb.append((char) ('a' + nextNumber() % 26));
return sb.toString();
}
static class Node {
final Node[] children = new Node[26];
}
static boolean hasPrefix(Node root, String p) {
Node node = root;
for (char c : p.toCharArray()) {
node = node.children[c - 'a'];
if (node == null) return false;
}
return true;
}
public static void main(String[] args) {
List<String> words = new ArrayList<>(), prefixes = new ArrayList<>();
for (int k = 0; k < 10000; k++) words.add(word(4 + nextNumber() % 7));
for (int k = 0; k < 1000; k++) prefixes.add(word(2 + nextNumber() % 4));
System.out.println(words.size() + " words, " + prefixes.size() + " prefixes asked");
long start = System.nanoTime();
int foundScan = 0;
for (String p : prefixes) {
for (String w : words) {
if (w.startsWith(p)) { // every word, until one starts with p
foundScan++;
break;
}
}
}
long scanMs = (System.nanoTime() - start) / 1000000;
start = System.nanoTime();
Node root = new Node();
int nodes = 0;
for (String w : words) {
Node node = root;
for (char c : w.toCharArray()) {
if (node.children[c - 'a'] == null) { // a prefix no word had before: one new node
node.children[c - 'a'] = new Node();
nodes++;
}
node = node.children[c - 'a'];
}
}
long buildMs = (System.nanoTime() - start) / 1000000;
start = System.nanoTime();
int foundTrie = 0;
for (String p : prefixes) if (hasPrefix(root, p)) foundTrie++;
long askMs = (System.nanoTime() - start) / 1000000;
System.out.println("found: " + foundScan + " by the scan, " + foundTrie + " by the trie");
int letters = 0;
for (String w : words) letters += w.length();
System.out.println("letters in the words: " + letters + " | trie nodes: " + nodes);
System.out.println("scan: " + scanMs + " ms | trie: " + buildMs + " ms to build, " + askMs + " ms to answer");
}
}
// 10000 words, 1000 prefixes asked
// found: 370 by the scan, 370 by the trie
// letters in the words: 69731 | trie nodes: 47955
// scan: 92 ms | trie: 28 ms to build, 0 ms to answer#include <bits/stdc++.h>
using namespace std;
long long x = 7; // the same words and prefixes in every language
int next_number() {
x = x * 48271 % 2147483647;
return (int) x;
}
string word(int length) {
string s;
for (int i = 0; i < length; i++) s += (char) ('a' + next_number() % 26);
return s;
}
struct Node {
Node* children[26] = {};
};
bool hasPrefix(Node* root, const string& p) {
Node* node = root;
for (char c : p) {
node = node->children[c - 'a'];
if (!node) return false;
}
return true;
}
long long msSince(chrono::steady_clock::time_point start) {
return chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count();
}
int main() {
vector<string> words, prefixes;
for (int k = 0; k < 10000; k++) words.push_back(word(4 + next_number() % 7));
for (int k = 0; k < 1000; k++) prefixes.push_back(word(2 + next_number() % 4));
cout << words.size() << " words, " << prefixes.size() << " prefixes asked\n";
auto start = chrono::steady_clock::now();
int foundScan = 0;
for (const string& p : prefixes) {
for (const string& w : words) {
if (w.compare(0, p.size(), p) == 0) { // every word, until one starts with p
foundScan++;
break;
}
}
}
long long scanMs = msSince(start);
start = chrono::steady_clock::now();
Node* root = new Node();
int nodes = 0;
for (const string& w : words) {
Node* node = root;
for (char c : w) {
if (!node->children[c - 'a']) { // a prefix no word had before: one new node
node->children[c - 'a'] = new Node();
nodes++;
}
node = node->children[c - 'a'];
}
}
long long buildMs = msSince(start);
start = chrono::steady_clock::now();
int foundTrie = 0;
for (const string& p : prefixes) if (hasPrefix(root, p)) foundTrie++;
long long askMs = msSince(start);
cout << "found: " << foundScan << " by the scan, " << foundTrie << " by the trie\n";
size_t letters = 0;
for (const string& w : words) letters += w.size();
cout << "letters in the words: " << letters << " | trie nodes: " << nodes << "\n";
cout << "scan: " << scanMs << " ms | trie: " << buildMs << " ms to build, " << askMs << " ms to answer\n";
}
// 10000 words, 1000 prefixes asked
// found: 370 by the scan, 370 by the trie
// letters in the words: 69731 | trie nodes: 47955
// scan: 31 ms | trie: 7 ms to build, 0 ms to answerlet x = 7; // the same words and prefixes in every language
function nextNumber() {
x = x * 48271 % 2147483647;
return x;
}
function word(length) {
let s = "";
for (let i = 0; i < length; i++) s += String.fromCharCode(97 + nextNumber() % 26);
return s;
}
class Node {
constructor() {
this.children = new Array(26).fill(null);
}
}
function hasPrefix(root, p) {
let node = root;
for (const c of p) {
node = node.children[c.charCodeAt(0) - 97];
if (node === null) return false;
}
return true;
}
const words = [], prefixes = [];
for (let k = 0; k < 10000; k++) words.push(word(4 + nextNumber() % 7));
for (let k = 0; k < 1000; k++) prefixes.push(word(2 + nextNumber() % 4));
console.log(`${words.length} words, ${prefixes.length} prefixes asked`);
let start = performance.now();
let foundScan = 0;
for (const p of prefixes) if (words.some((w) => w.startsWith(p))) foundScan++; // every word, until one starts with p
const scanMs = Math.round(performance.now() - start);
start = performance.now();
const root = new Node();
let nodes = 0;
for (const w of words) {
let node = root;
for (const c of w) {
const i = c.charCodeAt(0) - 97;
if (node.children[i] === null) { // a prefix no word had before: one new node
node.children[i] = new Node();
nodes++;
}
node = node.children[i];
}
}
const buildMs = Math.round(performance.now() - start);
start = performance.now();
let foundTrie = 0;
for (const p of prefixes) if (hasPrefix(root, p)) foundTrie++;
const askMs = Math.round(performance.now() - start);
console.log(`found: ${foundScan} by the scan, ${foundTrie} by the trie`);
const letters = words.reduce((sum, w) => sum + w.length, 0);
console.log(`letters in the words: ${letters} | trie nodes: ${nodes}`);
console.log(`scan: ${scanMs} ms | trie: ${buildMs} ms to build, ${askMs} ms to answer`);
// 10000 words, 1000 prefixes asked
// found: 370 by the scan, 370 by the trie
// letters in the words: 69731 | trie nodes: 47955
// scan: 125 ms | trie: 44 ms to build, 1 ms to answerlet x = 7; // the same words and prefixes in every language
function nextNumber(): number {
x = x * 48271 % 2147483647;
return x;
}
function word(length: number): string {
let s = "";
for (let i = 0; i < length; i++) s += String.fromCharCode(97 + nextNumber() % 26);
return s;
}
class TrieNode {
children: (TrieNode | null)[] = new Array(26).fill(null);
}
function hasPrefix(root: TrieNode, p: string): boolean {
let node: TrieNode | null = root;
for (const c of p) {
node = node.children[c.charCodeAt(0) - 97];
if (node === null) return false;
}
return true;
}
const words: string[] = [], prefixes: string[] = [];
for (let k = 0; k < 10000; k++) words.push(word(4 + nextNumber() % 7));
for (let k = 0; k < 1000; k++) prefixes.push(word(2 + nextNumber() % 4));
console.log(`${words.length} words, ${prefixes.length} prefixes asked`);
let start = performance.now();
let foundScan = 0;
for (const p of prefixes) if (words.some((w) => w.startsWith(p))) foundScan++; // every word, until one starts with p
const scanMs = Math.round(performance.now() - start);
start = performance.now();
const root = new TrieNode();
let nodes = 0;
for (const w of words) {
let node = root;
for (const c of w) {
const i = c.charCodeAt(0) - 97;
if (node.children[i] === null) { // a prefix no word had before: one new node
node.children[i] = new TrieNode();
nodes++;
}
node = node.children[i]!;
}
}
const buildMs = Math.round(performance.now() - start);
start = performance.now();
let foundTrie = 0;
for (const p of prefixes) if (hasPrefix(root, p)) foundTrie++;
const askMs = Math.round(performance.now() - start);
console.log(`found: ${foundScan} by the scan, ${foundTrie} by the trie`);
const letters = words.reduce((sum, w) => sum + w.length, 0);
console.log(`letters in the words: ${letters} | trie nodes: ${nodes}`);
console.log(`scan: ${scanMs} ms | trie: ${buildMs} ms to build, ${askMs} ms to answer`);
// 10000 words, 1000 prefixes asked
// found: 370 by the scan, 370 by the trie
// letters in the words: 69731 | trie nodes: 47955
// scan: 113 ms | trie: 44 ms to build, 1 ms to answerusing System;
using System.Collections.Generic;
using System.Diagnostics;
class Node {
public readonly Node[] Children = new Node[26];
}
class Program {
static long x = 7; // the same words and prefixes in every language
static int NextNumber() {
x = x * 48271 % 2147483647;
return (int) x;
}
static string Word(int length) {
var chars = new char[length];
for (int i = 0; i < length; i++) chars[i] = (char) ('a' + NextNumber() % 26);
return new string(chars);
}
static bool HasPrefix(Node root, string p) {
Node node = root;
foreach (char c in p) {
node = node.Children[c - 'a'];
if (node == null) return false;
}
return true;
}
static void Main() {
var words = new List<string>();
var prefixes = new List<string>();
for (int k = 0; k < 10000; k++) words.Add(Word(4 + NextNumber() % 7));
for (int k = 0; k < 1000; k++) prefixes.Add(Word(2 + NextNumber() % 4));
Console.WriteLine($"{words.Count} words, {prefixes.Count} prefixes asked");
var watch = Stopwatch.StartNew();
int foundScan = 0;
foreach (string p in prefixes) {
foreach (string w in words) {
if (w.StartsWith(p, StringComparison.Ordinal)) { // every word, until one starts with p
foundScan++;
break;
}
}
}
long scanMs = watch.ElapsedMilliseconds;
watch.Restart();
var root = new Node();
int nodes = 0;
foreach (string w in words) {
Node node = root;
foreach (char c in w) {
if (node.Children[c - 'a'] == null) { // a prefix no word had before: one new node
node.Children[c - 'a'] = new Node();
nodes++;
}
node = node.Children[c - 'a'];
}
}
long buildMs = watch.ElapsedMilliseconds;
watch.Restart();
int foundTrie = 0;
foreach (string p in prefixes) if (HasPrefix(root, p)) foundTrie++;
long askMs = watch.ElapsedMilliseconds;
Console.WriteLine($"found: {foundScan} by the scan, {foundTrie} by the trie");
int letters = 0;
foreach (string w in words) letters += w.Length;
Console.WriteLine($"letters in the words: {letters} | trie nodes: {nodes}");
Console.WriteLine($"scan: {scanMs} ms | trie: {buildMs} ms to build, {askMs} ms to answer");
}
}
// 10000 words, 1000 prefixes asked
// found: 370 by the scan, 370 by the trie
// letters in the words: 69731 | trie nodes: 47955
// scan: 56 ms | trie: 17 ms to build, 0 ms to answerpackage main
import (
"fmt"
"strings"
"time"
)
var x int64 = 7 // the same words and prefixes in every language
func nextNumber() int {
x = x * 48271 % 2147483647
return int(x)
}
func word(length int) string {
b := make([]byte, length)
for i := range b {
b[i] = byte('a' + nextNumber()%26)
}
return string(b)
}
type Node struct {
children [26]*Node
}
func hasPrefix(root *Node, p string) bool {
node := root
for i := 0; i < len(p); i++ {
node = node.children[p[i]-'a']
if node == nil {
return false
}
}
return true
}
func main() {
words, prefixes := []string{}, []string{}
for k := 0; k < 10000; k++ {
words = append(words, word(4+nextNumber()%7))
}
for k := 0; k < 1000; k++ {
prefixes = append(prefixes, word(2+nextNumber()%4))
}
fmt.Printf("%d words, %d prefixes asked\n", len(words), len(prefixes))
start := time.Now()
foundScan := 0
for _, p := range prefixes {
for _, w := range words {
if strings.HasPrefix(w, p) { // every word, until one starts with p
foundScan++
break
}
}
}
scanMs := time.Since(start).Milliseconds()
start = time.Now()
root := &Node{}
nodes := 0
for _, w := range words {
node := root
for i := 0; i < len(w); i++ {
c := w[i] - 'a'
if node.children[c] == nil { // a prefix no word had before: one new node
node.children[c] = &Node{}
nodes++
}
node = node.children[c]
}
}
buildMs := time.Since(start).Milliseconds()
start = time.Now()
foundTrie := 0
for _, p := range prefixes {
if hasPrefix(root, p) {
foundTrie++
}
}
askMs := time.Since(start).Milliseconds()
fmt.Printf("found: %d by the scan, %d by the trie\n", foundScan, foundTrie)
letters := 0
for _, w := range words {
letters += len(w)
}
fmt.Printf("letters in the words: %d | trie nodes: %d\n", letters, nodes)
fmt.Printf("scan: %d ms | trie: %d ms to build, %d ms to answer\n", scanMs, buildMs, askMs)
}
// 10000 words, 1000 prefixes asked
// found: 370 by the scan, 370 by the trie
// letters in the words: 69731 | trie nodes: 47955
// scan: 41 ms | trie: 16 ms to build, 0 ms to answerThe scan and the trie agreed in all seven languages: 370 of the 1,000 prefixes start some word. The scan took 372 ms in Python and 31 ms in C++. The trie took 66 ms to build in Python and 7 ms in C++, once, and then answered all 1,000 questions in 1 ms or less in every language. Even with its building counted, it was 2.5 to 5.6 times faster, and the next 1,000 keystrokes cost the scan the same again while the trie is already built.
The scan's trouble is the misses: the other 630 start no word, and for each of those it reads all 10,000 words to be sure. The trie answers any prefix by walking one node per letter, five at most here. It has 47,955 nodes below its root for the words' 69,731 letters: words that start alike share the nodes of the letters they start with.
One node per prefix
A trie (from retrieval, usually said like try to keep it apart from tree) is a tree where every node stands for a prefix. The root is the empty prefix. A node's children are that prefix followed by one more letter, so with lowercase letters a node has up to 26 children. A word is a path from the root, one node per letter, and the node where it ends carries an end mark: the path so far spells a whole word.
Three operations come with it:
- insert(word) walks the word's letters from the root, making a node wherever no word went before, and puts the end mark on the last one.
- search(word) walks the same way and needs two things: that the path exists and that its last node has the end mark.
- startsWith(prefix) only needs the path to exist.
Here they are on car, card, care, cat and dog:
class Node:
def __init__(self):
self.children = [None] * 26 # children[i] is the next letter, chr(ord("a") + i)
self.end = False # a word ends here
class Trie:
def __init__(self):
self.root = Node()
self.nodes = 1
def insert(self, word):
node = self.root
for c in word:
i = ord(c) - ord("a")
if node.children[i] is None: # no word so far went this way: make the node
node.children[i] = Node()
self.nodes += 1
node = node.children[i]
node.end = True
def walk(self, s): # the node at the end of s's path, or None if it falls off
node = self.root
for c in s:
node = node.children[ord(c) - ord("a")]
if node is None:
return None
return node
def search(self, word):
node = self.walk(word)
return node is not None and node.end
def starts_with(self, prefix):
return self.walk(prefix) is not None
def yes(b):
return "true" if b else "false"
t = Trie()
for w in ("car", "card", "care", "cat", "dog"):
t.insert(w)
print("nodes:", t.nodes)
for q in ("car", "ca", "cart", "do"):
print(f'search("{q}") = {yes(t.search(q))}, startsWith("{q}") = {yes(t.starts_with(q))}')
# nodes: 10
# search("car") = true, startsWith("car") = true
# search("ca") = false, startsWith("ca") = true
# search("cart") = false, startsWith("cart") = false
# search("do") = false, startsWith("do") = truepublic class Main {
static class Node {
final Node[] children = new Node[26]; // children[i] is the next letter, 'a' + i
boolean end; // a word ends here
}
static class Trie {
final Node root = new Node();
int nodes = 1;
void insert(String word) {
Node node = root;
for (char c : word.toCharArray()) {
if (node.children[c - 'a'] == null) { // no word so far went this way: make the node
node.children[c - 'a'] = new Node();
nodes++;
}
node = node.children[c - 'a'];
}
node.end = true;
}
Node walk(String s) { // the node at the end of s's path, or null if it falls off
Node node = root;
for (char c : s.toCharArray()) {
node = node.children[c - 'a'];
if (node == null) return null;
}
return node;
}
boolean search(String word) {
Node node = walk(word);
return node != null && node.end;
}
boolean startsWith(String prefix) {
return walk(prefix) != null;
}
}
public static void main(String[] args) {
Trie t = new Trie();
for (String w : new String[] {"car", "card", "care", "cat", "dog"}) t.insert(w);
System.out.println("nodes: " + t.nodes);
for (String q : new String[] {"car", "ca", "cart", "do"})
System.out.println("search(\"" + q + "\") = " + t.search(q) + ", startsWith(\"" + q + "\") = " + t.startsWith(q));
}
}
// nodes: 10
// search("car") = true, startsWith("car") = true
// search("ca") = false, startsWith("ca") = true
// search("cart") = false, startsWith("cart") = false
// search("do") = false, startsWith("do") = true#include <bits/stdc++.h>
using namespace std;
struct Node {
Node* children[26] = {}; // children[i] is the next letter, 'a' + i
bool end = false; // a word ends here
};
struct Trie {
Node* root = new Node();
int nodes = 1;
void insert(const string& word) {
Node* node = root;
for (char c : word) {
if (!node->children[c - 'a']) { // no word so far went this way: make the node
node->children[c - 'a'] = new Node();
nodes++;
}
node = node->children[c - 'a'];
}
node->end = true;
}
Node* walk(const string& s) { // the node at the end of s's path, or nullptr if it falls off
Node* node = root;
for (char c : s) {
node = node->children[c - 'a'];
if (!node) return nullptr;
}
return node;
}
bool search(const string& word) {
Node* node = walk(word);
return node && node->end;
}
bool startsWith(const string& prefix) {
return walk(prefix) != nullptr;
}
};
int main() {
Trie t;
for (string w : {"car", "card", "care", "cat", "dog"}) t.insert(w);
cout << "nodes: " << t.nodes << "\n" << boolalpha;
for (string q : {"car", "ca", "cart", "do"})
cout << "search(\"" << q << "\") = " << t.search(q) << ", startsWith(\"" << q << "\") = " << t.startsWith(q) << "\n";
}
// nodes: 10
// search("car") = true, startsWith("car") = true
// search("ca") = false, startsWith("ca") = true
// search("cart") = false, startsWith("cart") = false
// search("do") = false, startsWith("do") = trueclass Node {
constructor() {
this.children = new Array(26).fill(null); // children[i] is the next letter, 'a' + i
this.end = false; // a word ends here
}
}
class Trie {
constructor() {
this.root = new Node();
this.nodes = 1;
}
insert(word) {
let node = this.root;
for (const c of word) {
const i = c.charCodeAt(0) - 97;
if (node.children[i] === null) { // no word so far went this way: make the node
node.children[i] = new Node();
this.nodes++;
}
node = node.children[i];
}
node.end = true;
}
walk(s) { // the node at the end of s's path, or null if it falls off
let node = this.root;
for (const c of s) {
node = node.children[c.charCodeAt(0) - 97];
if (node === null) return null;
}
return node;
}
search(word) {
const node = this.walk(word);
return node !== null && node.end;
}
startsWith(prefix) {
return this.walk(prefix) !== null;
}
}
const t = new Trie();
for (const w of ["car", "card", "care", "cat", "dog"]) t.insert(w);
console.log("nodes:", t.nodes);
for (const q of ["car", "ca", "cart", "do"])
console.log(`search("${q}") = ${t.search(q)}, startsWith("${q}") = ${t.startsWith(q)}`);
// nodes: 10
// search("car") = true, startsWith("car") = true
// search("ca") = false, startsWith("ca") = true
// search("cart") = false, startsWith("cart") = false
// search("do") = false, startsWith("do") = trueclass TrieNode {
children: (TrieNode | null)[] = new Array(26).fill(null); // children[i] is the next letter, 'a' + i
end = false; // a word ends here
}
class Trie {
root = new TrieNode();
nodes = 1;
insert(word: string): void {
let node = this.root;
for (const c of word) {
const i = c.charCodeAt(0) - 97;
if (node.children[i] === null) { // no word so far went this way: make the node
node.children[i] = new TrieNode();
this.nodes++;
}
node = node.children[i]!;
}
node.end = true;
}
walk(s: string): TrieNode | null { // the node at the end of s's path, or null if it falls off
let node: TrieNode | null = this.root;
for (const c of s) {
node = node.children[c.charCodeAt(0) - 97];
if (node === null) return null;
}
return node;
}
search(word: string): boolean {
const node = this.walk(word);
return node !== null && node.end;
}
startsWith(prefix: string): boolean {
return this.walk(prefix) !== null;
}
}
const t = new Trie();
for (const w of ["car", "card", "care", "cat", "dog"]) t.insert(w);
console.log("nodes:", t.nodes);
for (const q of ["car", "ca", "cart", "do"])
console.log(`search("${q}") = ${t.search(q)}, startsWith("${q}") = ${t.startsWith(q)}`);
// nodes: 10
// search("car") = true, startsWith("car") = true
// search("ca") = false, startsWith("ca") = true
// search("cart") = false, startsWith("cart") = false
// search("do") = false, startsWith("do") = trueusing System;
class Node {
public readonly Node[] Children = new Node[26]; // Children[i] is the next letter, 'a' + i
public bool End; // a word ends here
}
class Trie {
readonly Node root = new Node();
public int Nodes = 1;
public void Insert(string word) {
Node node = root;
foreach (char c in word) {
if (node.Children[c - 'a'] == null) { // no word so far went this way: make the node
node.Children[c - 'a'] = new Node();
Nodes++;
}
node = node.Children[c - 'a'];
}
node.End = true;
}
Node Walk(string s) { // the node at the end of s's path, or null if it falls off
Node node = root;
foreach (char c in s) {
node = node.Children[c - 'a'];
if (node == null) return null;
}
return node;
}
public bool Search(string word) {
Node node = Walk(word);
return node != null && node.End;
}
public bool StartsWith(string prefix) {
return Walk(prefix) != null;
}
}
class Program {
static string Yes(bool b) => b ? "true" : "false";
static void Main() {
var t = new Trie();
foreach (string w in new[] {"car", "card", "care", "cat", "dog"}) t.Insert(w);
Console.WriteLine($"nodes: {t.Nodes}");
foreach (string q in new[] {"car", "ca", "cart", "do"})
Console.WriteLine($"search(\"{q}\") = {Yes(t.Search(q))}, startsWith(\"{q}\") = {Yes(t.StartsWith(q))}");
}
}
// nodes: 10
// search("car") = true, startsWith("car") = true
// search("ca") = false, startsWith("ca") = true
// search("cart") = false, startsWith("cart") = false
// search("do") = false, startsWith("do") = truepackage main
import "fmt"
type Node struct {
children [26]*Node // children[i] is the next letter, 'a' + i
end bool // a word ends here
}
type Trie struct {
root *Node
nodes int
}
func (t *Trie) Insert(word string) {
node := t.root
for i := 0; i < len(word); i++ {
c := word[i] - 'a'
if node.children[c] == nil { // no word so far went this way: make the node
node.children[c] = &Node{}
t.nodes++
}
node = node.children[c]
}
node.end = true
}
func (t *Trie) walk(s string) *Node { // the node at the end of s's path, or nil if it falls off
node := t.root
for i := 0; i < len(s); i++ {
node = node.children[s[i]-'a']
if node == nil {
return nil
}
}
return node
}
func (t *Trie) Search(word string) bool {
node := t.walk(word)
return node != nil && node.end
}
func (t *Trie) StartsWith(prefix string) bool {
return t.walk(prefix) != nil
}
func main() {
t := &Trie{root: &Node{}, nodes: 1}
for _, w := range []string{"car", "card", "care", "cat", "dog"} {
t.Insert(w)
}
fmt.Println("nodes:", t.nodes)
for _, q := range []string{"car", "ca", "cart", "do"} {
fmt.Printf("search(\"%s\") = %t, startsWith(\"%s\") = %t\n", q, t.Search(q), q, t.StartsWith(q))
}
}
// nodes: 10
// search("car") = true, startsWith("car") = true
// search("ca") = false, startsWith("ca") = true
// search("cart") = false, startsWith("cart") = false
// search("do") = false, startsWith("do") = trueTen nodes: the root and one per distinct prefix (c, ca, car, card, care, cat, d, do, dog). search("car") is true because car's node has the end mark, though card and care go on below it. search("ca") is false while startsWith("ca") is true: the path exists, but no word ends there. cart falls off the trie after car, which has no child t, so both are false.
Build the Trie. Insert words letter by letter, deciding at each step whether a node for the letter is already there, then answer searches by walking the paths yourself.
Why one path is enough
Every word that starts with a prefix p goes through the same node, the one at the end of p's path: two words share a node exactly when they share the prefix up to it. So a question about p never has to look anywhere else. startsWith walks p's letters and stops; search walks the word's letters and reads one mark.
That makes every operation O(L) for a word or prefix of length L, one step per letter, however many words the trie holds. The scan is O(n × L) per question, n words of up to L letters each. Memory is one node per distinct prefix, plus the root: never more than the total number of letters, and less when words share prefixes, as the 10,000 words above did.
A hash set holding every prefix of every word would answer startsWith in one lookup too. But a word of length L puts L prefixes in it, L(L+1)/2 letters in all, and a set can only say yes or no: it can't list the words that start with p, count them or give them in order.
What a trie doesn't do better: a question about a whole word only. A hash set of the words answers "is this a word?" in O(L) too, with less code and less memory. The trie earns its nodes when the question is about prefixes: does any word start with this, how many do, which ones, in what order.
An array of 26, or a map
A node's children can live in two ways:
| Children as | One step | Memory per node | Order of the children |
|---|---|---|---|
An array of 26, indexed by c - 'a' | O(1), one index | 26 slots, used or not | a to z, for free |
| A hash map from letter to child | O(1) on average, one hash | only the children that exist | none: sort them to get it |
The array is the usual choice for lowercase letters: the step is one index and a walk of the children visits them in alphabetical order, which the suggestions below use. Its cost is 26 slots in every node, most of them empty in a sparse trie. A map takes any alphabet (uppercase, digits, Unicode) and keeps only the children that exist. The array breaks on anything outside a to z: an uppercase letter, a digit or a space gives c - 'a' an index below 0 or past 25.
Counting words and prefixes
"How many words start with p?" and "how many times was this word inserted?" are the same walk with a number at the end. Give every node two counts: passing, how many words' paths go through it, and ending, how many words end there. insert adds 1 to passing on every node of the path and 1 to ending on the last. Then countWordsStartingWith(p) is the passing count at p's node and countWordsEqualTo(w) is the ending count at w's. erase walks the word and takes the 1s back off:
class Node:
def __init__(self):
self.children = [None] * 26
self.passing = 0 # words whose path goes through this node
self.ending = 0 # words that end here
class Trie:
def __init__(self):
self.root = Node()
def insert(self, word):
node = self.root
for c in word:
i = ord(c) - ord("a")
if node.children[i] is None:
node.children[i] = Node()
node = node.children[i]
node.passing += 1
node.ending += 1
def walk(self, s):
node = self.root
for c in s:
node = node.children[ord(c) - ord("a")]
if node is None:
return None
return node
def count_words_equal_to(self, word):
node = self.walk(word)
return node.ending if node else 0
def count_words_starting_with(self, prefix):
node = self.walk(prefix)
return node.passing if node else 0
def erase(self, word): # the word is in the trie: take it off every count on its path
node = self.root
for c in word:
node = node.children[ord(c) - ord("a")]
node.passing -= 1
node.ending -= 1
t = Trie()
for w in ("tap", "tap", "tape", "top"):
t.insert(w)
print(f'countWordsEqualTo("tap") = {t.count_words_equal_to("tap")}, '
f'countWordsStartingWith("ta") = {t.count_words_starting_with("ta")}')
t.erase("tap")
print(f'after erase("tap"): countWordsEqualTo("tap") = {t.count_words_equal_to("tap")}, '
f'countWordsStartingWith("ta") = {t.count_words_starting_with("ta")}, '
f'countWordsStartingWith("t") = {t.count_words_starting_with("t")}')
# countWordsEqualTo("tap") = 2, countWordsStartingWith("ta") = 3
# after erase("tap"): countWordsEqualTo("tap") = 1, countWordsStartingWith("ta") = 2, countWordsStartingWith("t") = 3public class Main {
static class Node {
final Node[] children = new Node[26];
int passing; // words whose path goes through this node
int ending; // words that end here
}
static class Trie {
final Node root = new Node();
void insert(String word) {
Node node = root;
for (char c : word.toCharArray()) {
if (node.children[c - 'a'] == null) node.children[c - 'a'] = new Node();
node = node.children[c - 'a'];
node.passing++;
}
node.ending++;
}
Node walk(String s) {
Node node = root;
for (char c : s.toCharArray()) {
node = node.children[c - 'a'];
if (node == null) return null;
}
return node;
}
int countWordsEqualTo(String word) {
Node node = walk(word);
return node == null ? 0 : node.ending;
}
int countWordsStartingWith(String prefix) {
Node node = walk(prefix);
return node == null ? 0 : node.passing;
}
void erase(String word) { // the word is in the trie: take it off every count on its path
Node node = root;
for (char c : word.toCharArray()) {
node = node.children[c - 'a'];
node.passing--;
}
node.ending--;
}
}
public static void main(String[] args) {
Trie t = new Trie();
for (String w : new String[] {"tap", "tap", "tape", "top"}) t.insert(w);
System.out.println("countWordsEqualTo(\"tap\") = " + t.countWordsEqualTo("tap")
+ ", countWordsStartingWith(\"ta\") = " + t.countWordsStartingWith("ta"));
t.erase("tap");
System.out.println("after erase(\"tap\"): countWordsEqualTo(\"tap\") = " + t.countWordsEqualTo("tap")
+ ", countWordsStartingWith(\"ta\") = " + t.countWordsStartingWith("ta")
+ ", countWordsStartingWith(\"t\") = " + t.countWordsStartingWith("t"));
}
}
// countWordsEqualTo("tap") = 2, countWordsStartingWith("ta") = 3
// after erase("tap"): countWordsEqualTo("tap") = 1, countWordsStartingWith("ta") = 2, countWordsStartingWith("t") = 3#include <bits/stdc++.h>
using namespace std;
struct Node {
Node* children[26] = {};
int passing = 0; // words whose path goes through this node
int ending = 0; // words that end here
};
struct Trie {
Node* root = new Node();
void insert(const string& word) {
Node* node = root;
for (char c : word) {
if (!node->children[c - 'a']) node->children[c - 'a'] = new Node();
node = node->children[c - 'a'];
node->passing++;
}
node->ending++;
}
Node* walk(const string& s) {
Node* node = root;
for (char c : s) {
node = node->children[c - 'a'];
if (!node) return nullptr;
}
return node;
}
int countWordsEqualTo(const string& word) {
Node* node = walk(word);
return node ? node->ending : 0;
}
int countWordsStartingWith(const string& prefix) {
Node* node = walk(prefix);
return node ? node->passing : 0;
}
void erase(const string& word) { // the word is in the trie: take it off every count on its path
Node* node = root;
for (char c : word) {
node = node->children[c - 'a'];
node->passing--;
}
node->ending--;
}
};
int main() {
Trie t;
for (string w : {"tap", "tap", "tape", "top"}) t.insert(w);
cout << "countWordsEqualTo(\"tap\") = " << t.countWordsEqualTo("tap")
<< ", countWordsStartingWith(\"ta\") = " << t.countWordsStartingWith("ta") << "\n";
t.erase("tap");
cout << "after erase(\"tap\"): countWordsEqualTo(\"tap\") = " << t.countWordsEqualTo("tap")
<< ", countWordsStartingWith(\"ta\") = " << t.countWordsStartingWith("ta")
<< ", countWordsStartingWith(\"t\") = " << t.countWordsStartingWith("t") << "\n";
}
// countWordsEqualTo("tap") = 2, countWordsStartingWith("ta") = 3
// after erase("tap"): countWordsEqualTo("tap") = 1, countWordsStartingWith("ta") = 2, countWordsStartingWith("t") = 3class Node {
constructor() {
this.children = new Array(26).fill(null);
this.passing = 0; // words whose path goes through this node
this.ending = 0; // words that end here
}
}
class Trie {
constructor() {
this.root = new Node();
}
insert(word) {
let node = this.root;
for (const c of word) {
const i = c.charCodeAt(0) - 97;
if (node.children[i] === null) node.children[i] = new Node();
node = node.children[i];
node.passing++;
}
node.ending++;
}
walk(s) {
let node = this.root;
for (const c of s) {
node = node.children[c.charCodeAt(0) - 97];
if (node === null) return null;
}
return node;
}
countWordsEqualTo(word) {
const node = this.walk(word);
return node === null ? 0 : node.ending;
}
countWordsStartingWith(prefix) {
const node = this.walk(prefix);
return node === null ? 0 : node.passing;
}
erase(word) { // the word is in the trie: take it off every count on its path
let node = this.root;
for (const c of word) {
node = node.children[c.charCodeAt(0) - 97];
node.passing--;
}
node.ending--;
}
}
const t = new Trie();
for (const w of ["tap", "tap", "tape", "top"]) t.insert(w);
console.log(`countWordsEqualTo("tap") = ${t.countWordsEqualTo("tap")}, countWordsStartingWith("ta") = ${t.countWordsStartingWith("ta")}`);
t.erase("tap");
console.log(`after erase("tap"): countWordsEqualTo("tap") = ${t.countWordsEqualTo("tap")}, ` +
`countWordsStartingWith("ta") = ${t.countWordsStartingWith("ta")}, countWordsStartingWith("t") = ${t.countWordsStartingWith("t")}`);
// countWordsEqualTo("tap") = 2, countWordsStartingWith("ta") = 3
// after erase("tap"): countWordsEqualTo("tap") = 1, countWordsStartingWith("ta") = 2, countWordsStartingWith("t") = 3class TrieNode {
children: (TrieNode | null)[] = new Array(26).fill(null);
passing = 0; // words whose path goes through this node
ending = 0; // words that end here
}
class Trie {
root = new TrieNode();
insert(word: string): void {
let node = this.root;
for (const c of word) {
const i = c.charCodeAt(0) - 97;
if (node.children[i] === null) node.children[i] = new TrieNode();
node = node.children[i]!;
node.passing++;
}
node.ending++;
}
walk(s: string): TrieNode | null {
let node: TrieNode | null = this.root;
for (const c of s) {
node = node.children[c.charCodeAt(0) - 97];
if (node === null) return null;
}
return node;
}
countWordsEqualTo(word: string): number {
const node = this.walk(word);
return node === null ? 0 : node.ending;
}
countWordsStartingWith(prefix: string): number {
const node = this.walk(prefix);
return node === null ? 0 : node.passing;
}
erase(word: string): void { // the word is in the trie: take it off every count on its path
let node = this.root;
for (const c of word) {
node = node.children[c.charCodeAt(0) - 97]!;
node.passing--;
}
node.ending--;
}
}
const t = new Trie();
for (const w of ["tap", "tap", "tape", "top"]) t.insert(w);
console.log(`countWordsEqualTo("tap") = ${t.countWordsEqualTo("tap")}, countWordsStartingWith("ta") = ${t.countWordsStartingWith("ta")}`);
t.erase("tap");
console.log(`after erase("tap"): countWordsEqualTo("tap") = ${t.countWordsEqualTo("tap")}, ` +
`countWordsStartingWith("ta") = ${t.countWordsStartingWith("ta")}, countWordsStartingWith("t") = ${t.countWordsStartingWith("t")}`);
// countWordsEqualTo("tap") = 2, countWordsStartingWith("ta") = 3
// after erase("tap"): countWordsEqualTo("tap") = 1, countWordsStartingWith("ta") = 2, countWordsStartingWith("t") = 3using System;
class Node {
public readonly Node[] Children = new Node[26];
public int Passing; // words whose path goes through this node
public int Ending; // words that end here
}
class Trie {
readonly Node root = new Node();
public void Insert(string word) {
Node node = root;
foreach (char c in word) {
if (node.Children[c - 'a'] == null) node.Children[c - 'a'] = new Node();
node = node.Children[c - 'a'];
node.Passing++;
}
node.Ending++;
}
Node Walk(string s) {
Node node = root;
foreach (char c in s) {
node = node.Children[c - 'a'];
if (node == null) return null;
}
return node;
}
public int CountWordsEqualTo(string word) => Walk(word)?.Ending ?? 0;
public int CountWordsStartingWith(string prefix) => Walk(prefix)?.Passing ?? 0;
public void Erase(string word) { // the word is in the trie: take it off every count on its path
Node node = root;
foreach (char c in word) {
node = node.Children[c - 'a'];
node.Passing--;
}
node.Ending--;
}
}
class Program {
static void Main() {
var t = new Trie();
foreach (string w in new[] {"tap", "tap", "tape", "top"}) t.Insert(w);
Console.WriteLine($"countWordsEqualTo(\"tap\") = {t.CountWordsEqualTo("tap")}, countWordsStartingWith(\"ta\") = {t.CountWordsStartingWith("ta")}");
t.Erase("tap");
Console.WriteLine($"after erase(\"tap\"): countWordsEqualTo(\"tap\") = {t.CountWordsEqualTo("tap")}, "
+ $"countWordsStartingWith(\"ta\") = {t.CountWordsStartingWith("ta")}, countWordsStartingWith(\"t\") = {t.CountWordsStartingWith("t")}");
}
}
// countWordsEqualTo("tap") = 2, countWordsStartingWith("ta") = 3
// after erase("tap"): countWordsEqualTo("tap") = 1, countWordsStartingWith("ta") = 2, countWordsStartingWith("t") = 3package main
import "fmt"
type Node struct {
children [26]*Node
passing int // words whose path goes through this node
ending int // words that end here
}
type Trie struct {
root *Node
}
func (t *Trie) Insert(word string) {
node := t.root
for i := 0; i < len(word); i++ {
c := word[i] - 'a'
if node.children[c] == nil {
node.children[c] = &Node{}
}
node = node.children[c]
node.passing++
}
node.ending++
}
func (t *Trie) walk(s string) *Node {
node := t.root
for i := 0; i < len(s); i++ {
node = node.children[s[i]-'a']
if node == nil {
return nil
}
}
return node
}
func (t *Trie) CountWordsEqualTo(word string) int {
if node := t.walk(word); node != nil {
return node.ending
}
return 0
}
func (t *Trie) CountWordsStartingWith(prefix string) int {
if node := t.walk(prefix); node != nil {
return node.passing
}
return 0
}
func (t *Trie) Erase(word string) { // the word is in the trie: take it off every count on its path
node := t.root
for i := 0; i < len(word); i++ {
node = node.children[word[i]-'a']
node.passing--
}
node.ending--
}
func main() {
t := &Trie{root: &Node{}}
for _, w := range []string{"tap", "tap", "tape", "top"} {
t.Insert(w)
}
fmt.Printf("countWordsEqualTo(\"tap\") = %d, countWordsStartingWith(\"ta\") = %d\n",
t.CountWordsEqualTo("tap"), t.CountWordsStartingWith("ta"))
t.Erase("tap")
fmt.Printf("after erase(\"tap\"): countWordsEqualTo(\"tap\") = %d, countWordsStartingWith(\"ta\") = %d, countWordsStartingWith(\"t\") = %d\n",
t.CountWordsEqualTo("tap"), t.CountWordsStartingWith("ta"), t.CountWordsStartingWith("t"))
}
// countWordsEqualTo("tap") = 2, countWordsStartingWith("ta") = 3
// after erase("tap"): countWordsEqualTo("tap") = 1, countWordsStartingWith("ta") = 2, countWordsStartingWith("t") = 3tap went in twice, so ending is 2 at its node, and three words pass through ta: tap, tap and tape. After erase("tap"), one tap is left, two words pass through ta, and three through t, top included. No node is removed: a node whose passing count is 0 is as good as gone, because every question reads the counts. That's what keeps erase safe for the other words on the path.
A dot matches any letter
Design Add and Search Words Data Structure adds one twist to search: a . in the query matches any letter. At a letter, the walk takes the one child it names. At a dot it can't choose, so it tries every child that exists, and the walk becomes a depth-first search:
class Node:
def __init__(self):
self.children = [None] * 26
self.end = False
class WordDictionary:
def __init__(self):
self.root = Node()
def add_word(self, word):
node = self.root
for c in word:
i = ord(c) - ord("a")
if node.children[i] is None:
node.children[i] = Node()
node = node.children[i]
node.end = True
def search(self, word):
def match(node, k): # can word[k:] be read from node down?
if k == len(word):
return node.end
if word[k] == ".": # any letter: try every child that exists
return any(child is not None and match(child, k + 1) for child in node.children)
child = node.children[ord(word[k]) - ord("a")]
return child is not None and match(child, k + 1)
return match(self.root, 0)
d = WordDictionary()
for w in ("map", "mop", "mud", "maps"):
d.add_word(w)
for q in ("m.p", ".u.", "..x", "m...", "m.."):
print(f'search("{q}") = {"true" if d.search(q) else "false"}')
# search("m.p") = true
# search(".u.") = true
# search("..x") = false
# search("m...") = true
# search("m..") = truepublic class Main {
static class Node {
final Node[] children = new Node[26];
boolean end;
}
static class WordDictionary {
final Node root = new Node();
void addWord(String word) {
Node node = root;
for (char c : word.toCharArray()) {
if (node.children[c - 'a'] == null) node.children[c - 'a'] = new Node();
node = node.children[c - 'a'];
}
node.end = true;
}
boolean search(String word) {
return match(root, word, 0);
}
boolean match(Node node, String word, int k) { // can word[k..] be read from node down?
if (k == word.length()) return node.end;
char c = word.charAt(k);
if (c == '.') { // any letter: try every child that exists
for (Node child : node.children)
if (child != null && match(child, word, k + 1)) return true;
return false;
}
Node child = node.children[c - 'a'];
return child != null && match(child, word, k + 1);
}
}
public static void main(String[] args) {
WordDictionary d = new WordDictionary();
for (String w : new String[] {"map", "mop", "mud", "maps"}) d.addWord(w);
for (String q : new String[] {"m.p", ".u.", "..x", "m...", "m.."})
System.out.println("search(\"" + q + "\") = " + d.search(q));
}
}
// search("m.p") = true
// search(".u.") = true
// search("..x") = false
// search("m...") = true
// search("m..") = true#include <bits/stdc++.h>
using namespace std;
struct Node {
Node* children[26] = {};
bool end = false;
};
struct WordDictionary {
Node* root = new Node();
void addWord(const string& word) {
Node* node = root;
for (char c : word) {
if (!node->children[c - 'a']) node->children[c - 'a'] = new Node();
node = node->children[c - 'a'];
}
node->end = true;
}
bool search(const string& word) {
return match(root, word, 0);
}
bool match(Node* node, const string& word, size_t k) { // can word[k..] be read from node down?
if (k == word.size()) return node->end;
if (word[k] == '.') { // any letter: try every child that exists
for (Node* child : node->children)
if (child && match(child, word, k + 1)) return true;
return false;
}
Node* child = node->children[word[k] - 'a'];
return child && match(child, word, k + 1);
}
};
int main() {
WordDictionary d;
for (string w : {"map", "mop", "mud", "maps"}) d.addWord(w);
cout << boolalpha;
for (string q : {"m.p", ".u.", "..x", "m...", "m.."})
cout << "search(\"" << q << "\") = " << d.search(q) << "\n";
}
// search("m.p") = true
// search(".u.") = true
// search("..x") = false
// search("m...") = true
// search("m..") = trueclass Node {
constructor() {
this.children = new Array(26).fill(null);
this.end = false;
}
}
class WordDictionary {
constructor() {
this.root = new Node();
}
addWord(word) {
let node = this.root;
for (const c of word) {
const i = c.charCodeAt(0) - 97;
if (node.children[i] === null) node.children[i] = new Node();
node = node.children[i];
}
node.end = true;
}
search(word) {
const match = (node, k) => { // can word[k..] be read from node down?
if (k === word.length) return node.end;
if (word[k] === ".") // any letter: try every child that exists
return node.children.some((child) => child !== null && match(child, k + 1));
const child = node.children[word.charCodeAt(k) - 97];
return child !== null && match(child, k + 1);
};
return match(this.root, 0);
}
}
const d = new WordDictionary();
for (const w of ["map", "mop", "mud", "maps"]) d.addWord(w);
for (const q of ["m.p", ".u.", "..x", "m...", "m.."]) console.log(`search("${q}") = ${d.search(q)}`);
// search("m.p") = true
// search(".u.") = true
// search("..x") = false
// search("m...") = true
// search("m..") = trueclass TrieNode {
children: (TrieNode | null)[] = new Array(26).fill(null);
end = false;
}
class WordDictionary {
root = new TrieNode();
addWord(word: string): void {
let node = this.root;
for (const c of word) {
const i = c.charCodeAt(0) - 97;
if (node.children[i] === null) node.children[i] = new TrieNode();
node = node.children[i]!;
}
node.end = true;
}
search(word: string): boolean {
const match = (node: TrieNode, k: number): boolean => { // can word[k..] be read from node down?
if (k === word.length) return node.end;
if (word[k] === ".") // any letter: try every child that exists
return node.children.some((child) => child !== null && match(child, k + 1));
const child = node.children[word.charCodeAt(k) - 97];
return child !== null && match(child, k + 1);
};
return match(this.root, 0);
}
}
const d = new WordDictionary();
for (const w of ["map", "mop", "mud", "maps"]) d.addWord(w);
for (const q of ["m.p", ".u.", "..x", "m...", "m.."]) console.log(`search("${q}") = ${d.search(q)}`);
// search("m.p") = true
// search(".u.") = true
// search("..x") = false
// search("m...") = true
// search("m..") = trueusing System;
class Node {
public readonly Node[] Children = new Node[26];
public bool End;
}
class WordDictionary {
readonly Node root = new Node();
public void AddWord(string word) {
Node node = root;
foreach (char c in word) {
if (node.Children[c - 'a'] == null) node.Children[c - 'a'] = new Node();
node = node.Children[c - 'a'];
}
node.End = true;
}
public bool Search(string word) => Match(root, word, 0);
bool Match(Node node, string word, int k) { // can word[k..] be read from node down?
if (k == word.Length) return node.End;
if (word[k] == '.') { // any letter: try every child that exists
foreach (Node child in node.Children)
if (child != null && Match(child, word, k + 1)) return true;
return false;
}
Node next = node.Children[word[k] - 'a'];
return next != null && Match(next, word, k + 1);
}
}
class Program {
static void Main() {
var d = new WordDictionary();
foreach (string w in new[] {"map", "mop", "mud", "maps"}) d.AddWord(w);
foreach (string q in new[] {"m.p", ".u.", "..x", "m...", "m.."})
Console.WriteLine($"search(\"{q}\") = {(d.Search(q) ? "true" : "false")}");
}
}
// search("m.p") = true
// search(".u.") = true
// search("..x") = false
// search("m...") = true
// search("m..") = truepackage main
import "fmt"
type Node struct {
children [26]*Node
end bool
}
type WordDictionary struct {
root *Node
}
func (d *WordDictionary) AddWord(word string) {
node := d.root
for i := 0; i < len(word); i++ {
c := word[i] - 'a'
if node.children[c] == nil {
node.children[c] = &Node{}
}
node = node.children[c]
}
node.end = true
}
func (d *WordDictionary) Search(word string) bool {
return match(d.root, word, 0)
}
func match(node *Node, word string, k int) bool { // can word[k:] be read from node down?
if k == len(word) {
return node.end
}
if word[k] == '.' { // any letter: try every child that exists
for _, child := range node.children {
if child != nil && match(child, word, k+1) {
return true
}
}
return false
}
child := node.children[word[k]-'a']
return child != nil && match(child, word, k+1)
}
func main() {
d := &WordDictionary{root: &Node{}}
for _, w := range []string{"map", "mop", "mud", "maps"} {
d.AddWord(w)
}
for _, q := range []string{"m.p", ".u.", "..x", "m...", "m.."} {
fmt.Printf("search(\"%s\") = %t\n", q, d.Search(q))
}
}
// search("m.p") = true
// search(".u.") = true
// search("..x") = false
// search("m...") = true
// search("m..") = truem.p takes m, then tries the children under it for the dot: the first, a, leads to a p with the end mark, map, and the search stops there. ..x tries every two-letter path, ma, mo and mu, and none has a child x, so it's false. m... finds maps. A query of letters only is still one path. Each dot multiplies the paths: k dots can try up to of them, which is why the problem keeps dots few and words short.
Walk down, then stop or collect
Many trie problems are a walk with something to do on the way. Two of the most common:
- Stop at the first word on the path. Replacing each word of a sentence by its shortest root (sunny by su when su is a root) walks the word and stops at the first node with an end mark.
- Walk down the prefix, then collect. Suggesting words for a typed prefix walks to the prefix's node and collects the words below it. With an array of 26, visiting the children from a to z gives the words in alphabetical order, so the first three found are the three smallest.
class Node:
def __init__(self):
self.children = [None] * 26
self.word = None # the word that ends here, if one does
def build(words):
root = Node()
for w in words:
node = root
for c in w:
i = ord(c) - ord("a")
if node.children[i] is None:
node.children[i] = Node()
node = node.children[i]
node.word = w
return root
def shortest_root(root, w): # walk down w and stop at the first word on the way
node = root
for c in w:
node = node.children[ord(c) - ord("a")]
if node is None:
return w
if node.word is not None:
return node.word
return w
def suggest(root, prefix, k=3): # walk down the prefix, then collect in letter order
node = root
for c in prefix:
node = node.children[ord(c) - ord("a")]
if node is None:
return []
found = []
def collect(n):
if len(found) == k:
return
if n.word is not None:
found.append(n.word)
for child in n.children: # a, b, c, ...: the words come out sorted
if child is not None:
collect(child)
collect(node)
return found
roots = build(["su", "sun", "moon", "star"])
print(" ".join(shortest_root(roots, w) for w in "sunny days and moonlit stars sustain us".split()))
shop = build(["mango", "mangrove", "map", "maple", "mars", "mask"])
for p in ("ma", "map", "mx"):
print(f'"{p}":', " ".join(suggest(shop, p)) or "nothing")
# su days and moon star su us
# "ma": mango mangrove map
# "map": map maple
# "mx": nothingimport java.util.*;
public class Main {
static class Node {
final Node[] children = new Node[26];
String word; // the word that ends here, if one does
}
static Node build(String... words) {
Node root = new Node();
for (String w : words) {
Node node = root;
for (char c : w.toCharArray()) {
if (node.children[c - 'a'] == null) node.children[c - 'a'] = new Node();
node = node.children[c - 'a'];
}
node.word = w;
}
return root;
}
static String shortestRoot(Node root, String w) { // walk down w and stop at the first word on the way
Node node = root;
for (char c : w.toCharArray()) {
node = node.children[c - 'a'];
if (node == null) return w;
if (node.word != null) return node.word;
}
return w;
}
static List<String> suggest(Node root, String prefix, int k) { // walk down the prefix, then collect in letter order
Node node = root;
for (char c : prefix.toCharArray()) {
node = node.children[c - 'a'];
if (node == null) return new ArrayList<>();
}
List<String> found = new ArrayList<>();
collect(node, k, found);
return found;
}
static void collect(Node n, int k, List<String> found) {
if (found.size() == k) return;
if (n.word != null) found.add(n.word);
for (Node child : n.children) // a, b, c, ...: the words come out sorted
if (child != null) collect(child, k, found);
}
public static void main(String[] args) {
Node roots = build("su", "sun", "moon", "star");
StringJoiner line = new StringJoiner(" ");
for (String w : "sunny days and moonlit stars sustain us".split(" ")) line.add(shortestRoot(roots, w));
System.out.println(line);
Node shop = build("mango", "mangrove", "map", "maple", "mars", "mask");
for (String p : new String[] {"ma", "map", "mx"}) {
List<String> s = suggest(shop, p, 3);
System.out.println("\"" + p + "\": " + (s.isEmpty() ? "nothing" : String.join(" ", s)));
}
}
}
// su days and moon star su us
// "ma": mango mangrove map
// "map": map maple
// "mx": nothing#include <bits/stdc++.h>
using namespace std;
struct Node {
Node* children[26] = {};
string word; // the word that ends here, if one does
};
Node* build(const vector<string>& words) {
Node* root = new Node();
for (const string& w : words) {
Node* node = root;
for (char c : w) {
if (!node->children[c - 'a']) node->children[c - 'a'] = new Node();
node = node->children[c - 'a'];
}
node->word = w;
}
return root;
}
string shortestRoot(Node* root, const string& w) { // walk down w and stop at the first word on the way
Node* node = root;
for (char c : w) {
node = node->children[c - 'a'];
if (!node) return w;
if (!node->word.empty()) return node->word;
}
return w;
}
void collect(Node* n, size_t k, vector<string>& found) {
if (found.size() == k) return;
if (!n->word.empty()) found.push_back(n->word);
for (Node* child : n->children) // a, b, c, ...: the words come out sorted
if (child) collect(child, k, found);
}
vector<string> suggest(Node* root, const string& prefix, size_t k) { // walk down the prefix, then collect in letter order
Node* node = root;
for (char c : prefix) {
node = node->children[c - 'a'];
if (!node) return {};
}
vector<string> found;
collect(node, k, found);
return found;
}
int main() {
Node* roots = build({"su", "sun", "moon", "star"});
istringstream sentence("sunny days and moonlit stars sustain us");
string w, line;
while (sentence >> w) line += (line.empty() ? "" : " ") + shortestRoot(roots, w);
cout << line << "\n";
Node* shop = build({"mango", "mangrove", "map", "maple", "mars", "mask"});
for (string p : {"ma", "map", "mx"}) {
vector<string> s = suggest(shop, p, 3);
string joined;
for (const string& x : s) joined += (joined.empty() ? "" : " ") + x;
cout << "\"" << p << "\": " << (s.empty() ? "nothing" : joined) << "\n";
}
}
// su days and moon star su us
// "ma": mango mangrove map
// "map": map maple
// "mx": nothingclass Node {
constructor() {
this.children = new Array(26).fill(null);
this.word = null; // the word that ends here, if one does
}
}
function build(words) {
const root = new Node();
for (const w of words) {
let node = root;
for (const c of w) {
const i = c.charCodeAt(0) - 97;
if (node.children[i] === null) node.children[i] = new Node();
node = node.children[i];
}
node.word = w;
}
return root;
}
function shortestRoot(root, w) { // walk down w and stop at the first word on the way
let node = root;
for (const c of w) {
node = node.children[c.charCodeAt(0) - 97];
if (node === null) return w;
if (node.word !== null) return node.word;
}
return w;
}
function suggest(root, prefix, k = 3) { // walk down the prefix, then collect in letter order
let node = root;
for (const c of prefix) {
node = node.children[c.charCodeAt(0) - 97];
if (node === null) return [];
}
const found = [];
const collect = (n) => {
if (found.length === k) return;
if (n.word !== null) found.push(n.word);
for (const child of n.children) // a, b, c, ...: the words come out sorted
if (child !== null) collect(child);
};
collect(node);
return found;
}
const roots = build(["su", "sun", "moon", "star"]);
console.log("sunny days and moonlit stars sustain us".split(" ").map((w) => shortestRoot(roots, w)).join(" "));
const shop = build(["mango", "mangrove", "map", "maple", "mars", "mask"]);
for (const p of ["ma", "map", "mx"]) console.log(`"${p}":`, suggest(shop, p).join(" ") || "nothing");
// su days and moon star su us
// "ma": mango mangrove map
// "map": map maple
// "mx": nothingclass TrieNode {
children: (TrieNode | null)[] = new Array(26).fill(null);
word: string | null = null; // the word that ends here, if one does
}
function build(words: string[]): TrieNode {
const root = new TrieNode();
for (const w of words) {
let node = root;
for (const c of w) {
const i = c.charCodeAt(0) - 97;
if (node.children[i] === null) node.children[i] = new TrieNode();
node = node.children[i]!;
}
node.word = w;
}
return root;
}
function shortestRoot(root: TrieNode, w: string): string { // walk down w and stop at the first word on the way
let node: TrieNode | null = root;
for (const c of w) {
node = node.children[c.charCodeAt(0) - 97];
if (node === null) return w;
if (node.word !== null) return node.word;
}
return w;
}
function suggest(root: TrieNode, prefix: string, k = 3): string[] { // walk down the prefix, then collect in letter order
let node: TrieNode | null = root;
for (const c of prefix) {
node = node.children[c.charCodeAt(0) - 97];
if (node === null) return [];
}
const found: string[] = [];
const collect = (n: TrieNode): void => {
if (found.length === k) return;
if (n.word !== null) found.push(n.word);
for (const child of n.children) // a, b, c, ...: the words come out sorted
if (child !== null) collect(child);
};
collect(node);
return found;
}
const roots = build(["su", "sun", "moon", "star"]);
console.log("sunny days and moonlit stars sustain us".split(" ").map((w) => shortestRoot(roots, w)).join(" "));
const shop = build(["mango", "mangrove", "map", "maple", "mars", "mask"]);
for (const p of ["ma", "map", "mx"]) console.log(`"${p}":`, suggest(shop, p).join(" ") || "nothing");
// su days and moon star su us
// "ma": mango mangrove map
// "map": map maple
// "mx": nothingusing System;
using System.Collections.Generic;
using System.Linq;
class Node {
public readonly Node[] Children = new Node[26];
public string Word; // the word that ends here, if one does
}
class Program {
static Node Build(params string[] words) {
var root = new Node();
foreach (string w in words) {
Node node = root;
foreach (char c in w) {
if (node.Children[c - 'a'] == null) node.Children[c - 'a'] = new Node();
node = node.Children[c - 'a'];
}
node.Word = w;
}
return root;
}
static string ShortestRoot(Node root, string w) { // walk down w and stop at the first word on the way
Node node = root;
foreach (char c in w) {
node = node.Children[c - 'a'];
if (node == null) return w;
if (node.Word != null) return node.Word;
}
return w;
}
static List<string> Suggest(Node root, string prefix, int k) { // walk down the prefix, then collect in letter order
Node node = root;
foreach (char c in prefix) {
node = node.Children[c - 'a'];
if (node == null) return new List<string>();
}
var found = new List<string>();
Collect(node, k, found);
return found;
}
static void Collect(Node n, int k, List<string> found) {
if (found.Count == k) return;
if (n.Word != null) found.Add(n.Word);
foreach (Node child in n.Children) // a, b, c, ...: the words come out sorted
if (child != null) Collect(child, k, found);
}
static void Main() {
Node roots = Build("su", "sun", "moon", "star");
Console.WriteLine(string.Join(" ", "sunny days and moonlit stars sustain us".Split(' ').Select(w => ShortestRoot(roots, w))));
Node shop = Build("mango", "mangrove", "map", "maple", "mars", "mask");
foreach (string p in new[] {"ma", "map", "mx"}) {
List<string> s = Suggest(shop, p, 3);
Console.WriteLine($"\"{p}\": " + (s.Count == 0 ? "nothing" : string.Join(" ", s)));
}
}
}
// su days and moon star su us
// "ma": mango mangrove map
// "map": map maple
// "mx": nothingpackage main
import (
"fmt"
"strings"
)
type Node struct {
children [26]*Node
word string // the word that ends here, if one does
}
func build(words ...string) *Node {
root := &Node{}
for _, w := range words {
node := root
for i := 0; i < len(w); i++ {
c := w[i] - 'a'
if node.children[c] == nil {
node.children[c] = &Node{}
}
node = node.children[c]
}
node.word = w
}
return root
}
func shortestRoot(root *Node, w string) string { // walk down w and stop at the first word on the way
node := root
for i := 0; i < len(w); i++ {
node = node.children[w[i]-'a']
if node == nil {
return w
}
if node.word != "" {
return node.word
}
}
return w
}
func collect(n *Node, k int, found *[]string) {
if len(*found) == k {
return
}
if n.word != "" {
*found = append(*found, n.word)
}
for _, child := range n.children { // a, b, c, ...: the words come out sorted
if child != nil {
collect(child, k, found)
}
}
}
func suggest(root *Node, prefix string, k int) []string { // walk down the prefix, then collect in letter order
node := root
for i := 0; i < len(prefix); i++ {
node = node.children[prefix[i]-'a']
if node == nil {
return nil
}
}
found := []string{}
collect(node, k, &found)
return found
}
func main() {
roots := build("su", "sun", "moon", "star")
out := []string{}
for _, w := range strings.Fields("sunny days and moonlit stars sustain us") {
out = append(out, shortestRoot(roots, w))
}
fmt.Println(strings.Join(out, " "))
shop := build("mango", "mangrove", "map", "maple", "mars", "mask")
for _, p := range []string{"ma", "map", "mx"} {
s := suggest(shop, p, 3)
shown := strings.Join(s, " ")
if len(s) == 0 {
shown = "nothing"
}
fmt.Printf("\"%s\": %s\n", p, shown)
}
}
// su days and moon star su us
// "ma": mango mangrove map
// "map": map maple
// "mx": nothingsunny stopped at su, the first root on its path, though sun is on it too, and sustain stopped at su as well. days, us and the word and have no root on their paths and stay as they are. Under ma, the collection went n before p before r and s, so it stopped after mango, mangrove and map. mx falls off the trie, so there's nothing to suggest.
Two more of the same kind. Complete String asks for the longest word all of whose prefixes are words: walk each word and check the end mark on every node of its path. Count Distinct Substrings via Trie inserts every suffix of a string: each distinct substring is the prefix of some suffix, so it's exactly one node, and the root is the empty one. The answer, empty substring included, is the number of nodes.
Spotting a trie problem
Clues that a trie is the tool:
- Prefixes. "starts with", "autocomplete", "suggest", "how many words begin with".
- A dictionary of words and many questions against it, each question about part of a word.
- The shortest or longest word along a path, like roots of words or a word built one letter at a time.
- Patterns with wildcards matched against a set of words.
Near misses that look like it:
- Whole-word questions only ("is this a word?", "how many times was it added?"): a hash map is simpler and as fast.
- One text searched for one pattern: that's string matching, KMP or Z, not a trie.
- The bits of numbers, like the largest XOR of two numbers: still a trie, but over the bits, in Bitwise Tries: Maximum XOR.
Mistakes that look right
Two of these are run below in every language. The others are just as common:
- search that forgets the end mark returns true for a prefix that isn't a word.
- erase that cuts a node off deletes every word below it too.
- The end mark one node too early, set before the last step instead of after it: insert("car") marks ca, so search("ca") says yes and search("car") says no.
- A wildcard search that gives up after the first child it tries: with map, mop and mud inserted, m.d tries a first, finds no d after ma and returns false before it reaches mud.
c - 'a'on a character outside a to z: an uppercase letter or a space indexes outside the array.
class Node:
def __init__(self):
self.children = [None] * 26
self.end = False
def insert(root, word):
node = root
for c in word:
i = ord(c) - ord("a")
if node.children[i] is None:
node.children[i] = Node()
node = node.children[i]
node.end = True
def walk(root, s):
node = root
for c in s:
node = node.children[ord(c) - ord("a")]
if node is None:
return None
return node
def yes(b):
return "true" if b else "false"
root = Node()
insert(root, "card")
wrong = walk(root, "car") is not None # the path exists, so "found"
right = walk(root, "car") is not None and walk(root, "car").end
print(f'only "card" inserted: search("car") without the end mark = {yes(wrong)}, with it = {yes(right)}')
root = Node()
insert(root, "car")
insert(root, "card")
parent = walk(root, "ca")
parent.children[ord("r") - ord("a")] = None # erase("car") by cutting its node off
print(f'"car" and "card" inserted, erase("car") cutting its node: search("card") = {yes(walk(root, "card") is not None)}')
# only "card" inserted: search("car") without the end mark = true, with it = false
# "car" and "card" inserted, erase("car") cutting its node: search("card") = falsepublic class Main {
static class Node {
final Node[] children = new Node[26];
boolean end;
}
static void insert(Node root, String word) {
Node node = root;
for (char c : word.toCharArray()) {
if (node.children[c - 'a'] == null) node.children[c - 'a'] = new Node();
node = node.children[c - 'a'];
}
node.end = true;
}
static Node walk(Node root, String s) {
Node node = root;
for (char c : s.toCharArray()) {
node = node.children[c - 'a'];
if (node == null) return null;
}
return node;
}
public static void main(String[] args) {
Node root = new Node();
insert(root, "card");
boolean wrong = walk(root, "car") != null; // the path exists, so "found"
boolean right = walk(root, "car") != null && walk(root, "car").end;
System.out.println("only \"card\" inserted: search(\"car\") without the end mark = " + wrong + ", with it = " + right);
root = new Node();
insert(root, "car");
insert(root, "card");
walk(root, "ca").children['r' - 'a'] = null; // erase("car") by cutting its node off
System.out.println("\"car\" and \"card\" inserted, erase(\"car\") cutting its node: search(\"card\") = " + (walk(root, "card") != null));
}
}
// only "card" inserted: search("car") without the end mark = true, with it = false
// "car" and "card" inserted, erase("car") cutting its node: search("card") = false#include <bits/stdc++.h>
using namespace std;
struct Node {
Node* children[26] = {};
bool end = false;
};
void insert(Node* root, const string& word) {
Node* node = root;
for (char c : word) {
if (!node->children[c - 'a']) node->children[c - 'a'] = new Node();
node = node->children[c - 'a'];
}
node->end = true;
}
Node* walk(Node* root, const string& s) {
Node* node = root;
for (char c : s) {
node = node->children[c - 'a'];
if (!node) return nullptr;
}
return node;
}
int main() {
cout << boolalpha;
Node* root = new Node();
insert(root, "card");
bool wrong = walk(root, "car") != nullptr; // the path exists, so "found"
bool right = walk(root, "car") != nullptr && walk(root, "car")->end;
cout << "only \"card\" inserted: search(\"car\") without the end mark = " << wrong << ", with it = " << right << "\n";
root = new Node();
insert(root, "car");
insert(root, "card");
walk(root, "ca")->children['r' - 'a'] = nullptr; // erase("car") by cutting its node off
cout << "\"car\" and \"card\" inserted, erase(\"car\") cutting its node: search(\"card\") = " << (walk(root, "card") != nullptr) << "\n";
}
// only "card" inserted: search("car") without the end mark = true, with it = false
// "car" and "card" inserted, erase("car") cutting its node: search("card") = falseclass Node {
constructor() {
this.children = new Array(26).fill(null);
this.end = false;
}
}
function insert(root, word) {
let node = root;
for (const c of word) {
const i = c.charCodeAt(0) - 97;
if (node.children[i] === null) node.children[i] = new Node();
node = node.children[i];
}
node.end = true;
}
function walk(root, s) {
let node = root;
for (const c of s) {
node = node.children[c.charCodeAt(0) - 97];
if (node === null) return null;
}
return node;
}
let root = new Node();
insert(root, "card");
const wrong = walk(root, "car") !== null; // the path exists, so "found"
const right = walk(root, "car") !== null && walk(root, "car").end;
console.log(`only "card" inserted: search("car") without the end mark = ${wrong}, with it = ${right}`);
root = new Node();
insert(root, "car");
insert(root, "card");
walk(root, "ca").children["r".charCodeAt(0) - 97] = null; // erase("car") by cutting its node off
console.log(`"car" and "card" inserted, erase("car") cutting its node: search("card") = ${walk(root, "card") !== null}`);
// only "card" inserted: search("car") without the end mark = true, with it = false
// "car" and "card" inserted, erase("car") cutting its node: search("card") = falseclass TrieNode {
children: (TrieNode | null)[] = new Array(26).fill(null);
end = false;
}
function insert(root: TrieNode, word: string): void {
let node = root;
for (const c of word) {
const i = c.charCodeAt(0) - 97;
if (node.children[i] === null) node.children[i] = new TrieNode();
node = node.children[i]!;
}
node.end = true;
}
function walk(root: TrieNode, s: string): TrieNode | null {
let node: TrieNode | null = root;
for (const c of s) {
node = node.children[c.charCodeAt(0) - 97];
if (node === null) return null;
}
return node;
}
let root = new TrieNode();
insert(root, "card");
const wrong = walk(root, "car") !== null; // the path exists, so "found"
const right = walk(root, "car") !== null && walk(root, "car")!.end;
console.log(`only "card" inserted: search("car") without the end mark = ${wrong}, with it = ${right}`);
root = new TrieNode();
insert(root, "car");
insert(root, "card");
walk(root, "ca")!.children["r".charCodeAt(0) - 97] = null; // erase("car") by cutting its node off
console.log(`"car" and "card" inserted, erase("car") cutting its node: search("card") = ${walk(root, "card") !== null}`);
// only "card" inserted: search("car") without the end mark = true, with it = false
// "car" and "card" inserted, erase("car") cutting its node: search("card") = falseusing System;
class Node {
public readonly Node[] Children = new Node[26];
public bool End;
}
class Program {
static void Insert(Node root, string word) {
Node node = root;
foreach (char c in word) {
if (node.Children[c - 'a'] == null) node.Children[c - 'a'] = new Node();
node = node.Children[c - 'a'];
}
node.End = true;
}
static Node Walk(Node root, string s) {
Node node = root;
foreach (char c in s) {
node = node.Children[c - 'a'];
if (node == null) return null;
}
return node;
}
static string Yes(bool b) => b ? "true" : "false";
static void Main() {
var root = new Node();
Insert(root, "card");
bool wrong = Walk(root, "car") != null; // the path exists, so "found"
bool right = Walk(root, "car") != null && Walk(root, "car").End;
Console.WriteLine($"only \"card\" inserted: search(\"car\") without the end mark = {Yes(wrong)}, with it = {Yes(right)}");
root = new Node();
Insert(root, "car");
Insert(root, "card");
Walk(root, "ca").Children['r' - 'a'] = null; // erase("car") by cutting its node off
Console.WriteLine($"\"car\" and \"card\" inserted, erase(\"car\") cutting its node: search(\"card\") = {Yes(Walk(root, "card") != null)}");
}
}
// only "card" inserted: search("car") without the end mark = true, with it = false
// "car" and "card" inserted, erase("car") cutting its node: search("card") = falsepackage main
import "fmt"
type Node struct {
children [26]*Node
end bool
}
func insert(root *Node, word string) {
node := root
for i := 0; i < len(word); i++ {
c := word[i] - 'a'
if node.children[c] == nil {
node.children[c] = &Node{}
}
node = node.children[c]
}
node.end = true
}
func walk(root *Node, s string) *Node {
node := root
for i := 0; i < len(s); i++ {
node = node.children[s[i]-'a']
if node == nil {
return nil
}
}
return node
}
func main() {
root := &Node{}
insert(root, "card")
wrong := walk(root, "car") != nil // the path exists, so "found"
right := walk(root, "car") != nil && walk(root, "car").end
fmt.Printf("only \"card\" inserted: search(\"car\") without the end mark = %t, with it = %t\n", wrong, right)
root = &Node{}
insert(root, "car")
insert(root, "card")
walk(root, "ca").children['r'-'a'] = nil // erase("car") by cutting its node off
fmt.Printf("\"car\" and \"card\" inserted, erase(\"car\") cutting its node: search(\"card\") = %t\n", walk(root, "card") != nil)
}
// only "card" inserted: search("car") without the end mark = true, with it = false
// "car" and "card" inserted, erase("car") cutting its node: search("card") = falseWith only card inserted, the path c, a, r exists, so a search that only checks the path says car is a word. Cutting car's node off to erase it took card with it, since card's path goes through that node. With counts, erase only lowers numbers, and card is untouched.
Check yourself
Quiz
1 / 6Multiple choice
A trie of lowercase letters gets insert("pen"), insert("pencil") and insert("pent"). How many nodes does it have besides the root?
Multiple choice
A trie holds only "planet". Which of these returns true?
Multiple choice
A trie with passing and ending counts gets insert("bee") twice and insert("been") once, then erase("bee"). What does countWordsStartingWith("bee") return now?
Multiple choice
A WordDictionary holds cot, cut and cup. Which search returns false?
Multiple choice
The roots are be, bet and better. Which root replaces "betting" when every word takes its shortest root?
Multiple choice
A trie whose children are an array of 26, indexed by
ord(c) - ord("a"), gets insert("Cat"). What goes wrong?Practice
The section's problems, each mapped to the idea it trains:
- Implement Trie (Prefix Tree): insert, search and startsWith.
- Complete String (All Prefixes Exist): the end mark on every node of a path.
- Design Add and Search Words Data Structure: a dot that tries every child.
- Count Distinct Substrings via Trie: every suffix inserted, one node per distinct substring.
- Enhanced Trie with Count: passing and ending counts, and erase by decrements.