Lesson 130 of 164
Find All Words Stored in a Trie
Given a trie, return every word it contains. Visiting children from a to z returns the words in sorted (lexicographic) order.
Example
insert: "the", "a", "there", "answer", "any", "by", "bye", "their"
Output: ["a", "answer", "any", "by", "bye", "the", "their", "there"]A trie doesn't store whole words, only one character per edge. So each word has to be rebuilt from the characters on the path from the root to its end node.
Brute force: a new String at every node
Walk the trie depth-first, passing the prefix spelled so far as a String. For each child, create a new, longer string with prefix + letter. When a node has isEnd set, the current prefix is a word. A trie node is an object with an array of 26 child references, where null means "no such child".
import java.util.ArrayList;
import java.util.List;
public class Main {
static class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEnd;
}
static void insert(TrieNode root, String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
int idx = word.charAt(i) - 'a';
if (node.children[idx] == null) node.children[idx] = new TrieNode();
node = node.children[idx];
}
node.isEnd = true;
}
static void collect(TrieNode node, String prefix, List<String> out) {
if (node.isEnd) {
out.add(prefix);
}
for (int i = 0; i < 26; i++) {
if (node.children[i] != null) {
char letter = (char) ('a' + i);
collect(node.children[i], prefix + letter, out);
}
}
}
public static void main(String[] args) {
TrieNode root = new TrieNode();
for (String w : new String[] {"the", "a", "there", "answer", "any", "by", "bye", "their"}) {
insert(root, w);
}
List<String> words = new ArrayList<>();
collect(root, "", words);
System.out.println(words);
}
}[a, answer, any, by, bye, the, their, there]String is immutable, so prefix + letter copies the prefix into a new string. Adding a word to out needs no copy, because the string is never changed afterwards.
Time: O(N · L): each of the N nodes allocates and copies a prefix of up to L characters. Space: O(L²) for the strings alive along the current path, plus the output.
Optimal: one shared buffer, append and delete
Use a single StringBuilder as a buffer for the current path. Before visiting a child, append its letter to the buffer. After the child returns, delete the last character. The buffer always holds exactly the path from the root to the current node. Copy it with toString() only when a word ends there.
This append, recurse, delete pattern is called backtracking.
Walkthrough of the first few steps:
| action | buffer | output |
|---|---|---|
append a, visit |
"a" | ["a"] (end node) |
append n, visit |
"an" | |
append s … r, visit |
"answer" | ["a", "answer"] |
| delete back to "an" | "an" | |
append y, visit |
"any" | ["a", "answer", "any"] |
| delete back to "" | "" | |
append b … |
"b" |
import java.util.ArrayList;
import java.util.List;
public class Main {
static class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEnd;
}
static void insert(TrieNode root, String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
int idx = word.charAt(i) - 'a';
if (node.children[idx] == null) node.children[idx] = new TrieNode();
node = node.children[idx];
}
node.isEnd = true;
}
static void collect(TrieNode node, StringBuilder buf, List<String> out) {
if (node.isEnd) {
out.add(buf.toString());
}
for (int i = 0; i < 26; i++) {
if (node.children[i] != null) {
buf.append((char) ('a' + i));
collect(node.children[i], buf, out);
buf.deleteCharAt(buf.length() - 1);
}
}
}
public static void main(String[] args) {
TrieNode root = new TrieNode();
for (String w : new String[] {"the", "a", "there", "answer", "any", "by", "bye", "their"}) {
insert(root, w);
}
List<String> words = new ArrayList<>();
collect(root, new StringBuilder(), words);
System.out.println(words);
}
}[a, answer, any, by, bye, the, their, there]Time: O(N · 26 + total length of the output). Space: O(L) for the buffer and the recursion, plus the output.
Autocomplete: words with a given prefix
To list only the words that start with a prefix, walk down to the prefix's node first, then run the same collect from there, with the buffer starting as the prefix:
import java.util.ArrayList;
import java.util.List;
public class Main {
static class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEnd;
}
static void insert(TrieNode root, String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
int idx = word.charAt(i) - 'a';
if (node.children[idx] == null) node.children[idx] = new TrieNode();
node = node.children[idx];
}
node.isEnd = true;
}
static void collect(TrieNode node, StringBuilder buf, List<String> out) {
if (node.isEnd) {
out.add(buf.toString());
}
for (int i = 0; i < 26; i++) {
if (node.children[i] != null) {
buf.append((char) ('a' + i));
collect(node.children[i], buf, out);
buf.deleteCharAt(buf.length() - 1);
}
}
}
static List<String> autocomplete(TrieNode root, String prefix) {
TrieNode node = root;
for (int i = 0; i < prefix.length(); i++) {
node = node.children[prefix.charAt(i) - 'a'];
if (node == null) return new ArrayList<>(); // no word has this prefix
}
List<String> out = new ArrayList<>();
collect(node, new StringBuilder(prefix), out);
return out;
}
public static void main(String[] args) {
TrieNode root = new TrieNode();
for (String w : new String[] {"the", "a", "there", "answer", "any", "by", "bye", "their"}) {
insert(root, w);
}
System.out.println(autocomplete(root, "the"));
System.out.println(autocomplete(root, "an"));
System.out.println(autocomplete(root, "x"));
}
}[the, their, there]
[answer, any]
[]Time: O(P) to reach the prefix's node (P is the prefix length), plus the size of the subtree below it. Words without the prefix are never visited.