SyntaxPilot
Courses/DSA and Coding Problems/Lesson 45
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 45 of 90

Tries: implement a trie, then Word Search II (hard)

queued

These are the notes for DSA episode 45. Today we invent a new tree, the trie (say "try"), the tree behind every autocomplete box. In a trie, words that begin with the same letters share the same path, so a prefix check costs one step per letter, however many words are stored. We start from a real-life problem (a phone keyboard suggesting words as you type), define every word from zero, solve Implement Trie the obvious way (a list of words), watch it hit Time Limit Exceeded on 1 lakh words and 1 lakh prefix checks, and then build the trie: O(L) per operation, milliseconds for the same test. Then we use the trie to crack a famous hard problem, Word Search II: find every dictionary word on a letter grid by walking the grid and the trie together. Every program below was run with javac 21 with an 8-second limit (like the SyntaxPilot compiler), and every output shown is real.

The problem, in real life

Open your phone's keyboard and type c, then a. Instantly it suggests cat, car, cart. Those suggestions come from a dictionary of about 1 lakh (100,000) words stored inside the phone. The obvious way is to go through all 1 lakh words on every key press and check which ones begin with what you have typed. But it has to feel instant, on every key, for every user, on a small battery.

A paper dictionary already shows the better way. To find cart you don't read every page: you jump to the C thumb tab, then to the CA pages, and a bold headword tells you a real word ends there.

In real life In code
The letters you have typed so far a prefix
The phone's word list the dictionary we insert into
"Does any word begin with c-a?" startsWith("ca")
"Is cart a real word?" search("cart")
The C tab, then the CA pages the path root → c → a in the trie
A bold headword the end mark on a node
A newspaper word-search puzzle Word Search II: a grid of letters and a word list

Every word, from zero

  • Prefix: the beginning of a word, its first few letters. "ca" is a prefix of cat, car and cart; "at" is not a prefix of cat (it is at the end, not the beginning). The empty prefix "" (no letters at all) is a prefix of every word.
  • Tree, node, root, children: a tree is made of nodes linked downwards. The top node is the root; the nodes one step below a node are its children.
  • Trie: a tree of letters. Each step down from a node is one more letter. Words that share a beginning share the same path, so the beginning is stored once.
  • End mark: a flag on a node meaning "a real word ends here". Without it you can't tell the word app from the mere prefix app of apple.
  • insert(w) / search(w) / startsWith(p): add a word / is this exact word stored? / does any stored word begin with p?
  • ch - 'a': characters are numbers underneath, so 'c' - 'a' is 2. It turns a lowercase letter into a slot number 0…25.
  • null: "no object here". A null child means no stored word continues with that letter.
  • Grid, neighbour: a table of letters in rows and columns; a square's neighbours are the squares directly up, down, left and right (not diagonal).
  • DFS (depth-first search): follow one path as deep as it goes, then come back and try the next direction. Episode 35 (Word Search) used it to look for one word.
  • Backtracking and the visited mark: while a path is being explored we overwrite its squares with '#' so they can't be reused, and put the letters back on the way out.
  • Pruning: cutting off a path as soon as we know it can't lead to an answer.
  • O(L), O(n · L): costs, where n is the number of words and L the length of the word or prefix.
  • Lakh, crore: Indian number words: 1 lakh = 100,000; 1 crore = 10,000,000.

Problem 1: Implement Trie (LeetCode 208)

Design a class Trie with:

  • void insert(String w): add the word w;
  • boolean search(String w): true if the exact word w was inserted;
  • boolean startsWith(String p): true if some inserted word begins with p.
Calls Result
insert("apple"), search("apple") true
search("app") false (app was never inserted as a word)
startsWith("app") true (apple begins with app)
insert("app"), search("app") true

Constraints: lowercase letters a–z only, words up to 2,000 letters, up to 30,000 calls in total. We test much harder: 1 lakh words and 1 lakh prefix checks.

Brute force: a list of words

insert adds the word to an ArrayList (O(1)). search calls contains, which compares the word with every word in the list. startsWith loops over every word and asks Java's String.startsWith. Every query looks at the whole dictionary.

import java.util.*;

public class Main {
    static class SlowTrie {
        List<String> words = new ArrayList<>();
        void insert(String w) { words.add(w); }
        boolean search(String w) { return words.contains(w); }
        boolean startsWith(String p) {
            for (String w : words)
                if (w.startsWith(p)) return true;
            return false;
        }
    }
    public static void main(String[] args) {
        SlowTrie t = new SlowTrie();
        t.insert("apple");
        System.out.println(t.search("apple") + " " + t.search("app") + " " + t.startsWith("app"));
        t.insert("app");
        System.out.println(t.search("app"));
        System.out.println(t.startsWith("") + " " + t.search("b") + " " + t.startsWith("applesauce"));
    }
}

Real output:

true false true
true
true false false

The LeetCode example, then three edge cases: the empty prefix (true), a word that isn't there (false), and a prefix longer than any word (false). All correct.

1 lakh words, 1 lakh prefix checks: Time Limit Exceeded

        Random rnd = new Random(45);
        SlowTrie t = new SlowTrie();
        for (int i = 0; i < 100000; i++) {
            StringBuilder sb = new StringBuilder();
            for (int k = 0; k < 8; k++) sb.append((char) ('a' + rnd.nextInt(26)));
            t.insert(sb.toString());
        }
        long t0 = System.nanoTime();
        int found = 0;
        for (int q = 0; q < 100000; q++)
            if (t.startsWith("zzz" + (char) ('a' + q % 26))) found++;
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println(found + " found, " + ms + " ms");

One lakh random eight-letter words, then one lakh prefix checks (like a lakh key presses), all starting with zzz, which very few words do, so most checks scan the whole list. In the SyntaxPilot compiler: Time Limit Exceeded (stopped after 8 s). It printed nothing.

Why it is slow

  • Each startsWith checks all n words, and each check compares up to L letters: O(n · L) per query.
  • 1 lakh queries × 1 lakh words = 1,000 crore (10^10) word checks.
  • And look at the waste: cat, car and cart are checked one by one, even though all three begin with the same two letters, c-a.

The question: what if words that share a beginning also shared the work?

The key insight: a tree of letters

Build the trie for cat, car, cart and dog (★ = end mark):

            root
           /    \
          c      d
          |      |
          a      o
         / \     |
       t★   r★   g★
            |
            t★
  • Insert cat: a node for c, a child a, a child t, and a star on t.
  • Insert car: c and a are already there, so we reuse them and add only r (with a star). cart reuses c, a, r and adds t. Shared beginnings are stored once.
  • Insert dog: a new branch straight from the root.
  • startsWith("ca") walks two steps: c, then a. It does not matter whether the dictionary has ten words or ten lakh. search("ca") walks to the same node but finds no star, so it is false.

A trie node, in code

    static class Node {
        Node[] next = new Node[26];   // next[0] is the child for 'a', next[25] for 'z'
        boolean end;                  // the end mark
    }

The slot of a letter is ch - 'a' ('c' - 'a' is 2). A null slot means no word continues with that letter, so we can stop right there. Insert, search and startsWith all take one step per letter: O(L).

The optimal solution in Java

import java.util.*;

public class Main {
    static class Node {
        Node[] next = new Node[26];
        boolean end;
    }
    static class Trie {
        Node root = new Node();
        void insert(String w) {
            Node cur = root;
            for (char ch : w.toCharArray()) {
                int i = ch - 'a';
                if (cur.next[i] == null) cur.next[i] = new Node();
                cur = cur.next[i];
            }
            cur.end = true;
        }
        Node walk(String s) {
            Node cur = root;
            for (char ch : s.toCharArray()) {
                cur = cur.next[ch - 'a'];
                if (cur == null) return null;
            }
            return cur;
        }
        boolean search(String w) { Node n = walk(w); return n != null && n.end; }
        boolean startsWith(String p) { return walk(p) != null; }
    }
    public static void main(String[] args) {
        Trie t = new Trie();
        t.insert("apple");
        System.out.println(t.search("apple") + " " + t.search("app") + " " + t.startsWith("app"));
        t.insert("app");
        System.out.println(t.search("app"));
        System.out.println(t.startsWith("") + " " + t.search("b") + " " + t.startsWith("applesauce"));
    }
}
  • insert starts at the root. For each letter it finds the slot, creates the child if it is missing, and steps down. After the last letter it sets end = true.
  • walk follows the letters of s from the root and returns the node it reaches, or null as soon as a child is missing.
  • search: the node must exist and have the end mark. startsWith: the node just has to exist. For "", walk returns the root itself, so startsWith("") is true.

Real output:

true false true
true
true false false

Exactly the same answers as the list.

1 lakh words, 1 lakh checks in milliseconds

The same test as the brute force; only one line changes, Trie t = new Trie(); instead of SlowTrie. Real output:

19231 found, 51 ms

19,231 of the prefixes matched a word, and every check walked at most four nodes, one per letter.

The same solution in C++

#include <bits/stdc++.h>
using namespace std;

struct Node {
    Node* next[26] = {};
    bool end = false;
};

class Trie {
    Node* root = new Node();
    Node* walk(const string& s) {
        Node* cur = root;
        for (char ch : s) {
            cur = cur->next[ch - 'a'];
            if (!cur) return nullptr;
        }
        return cur;
    }
public:
    void insert(const string& w) {
        Node* cur = root;
        for (char ch : w) {
            int i = ch - 'a';
            if (!cur->next[i]) cur->next[i] = new Node();
            cur = cur->next[i];
        }
        cur->end = true;
    }
    bool search(const string& w) { Node* n = walk(w); return n && n->end; }
    bool startsWith(const string& p) { return walk(p) != nullptr; }
};

int main() {
    cout << boolalpha;
    Trie t;
    t.insert("apple");
    cout << t.search("apple") << " " << t.search("app") << " " << t.startsWith("app") << "\n";
    t.insert("app");
    cout << t.search("app") << "\n";
    cout << t.startsWith("") << " " << t.search("b") << " " << t.startsWith("applesauce") << "\n";

    mt19937 rnd(45);
    Trie big;
    for (int i = 0; i < 100000; i++) {
        string w;
        for (int k = 0; k < 8; k++) w += char('a' + rnd() % 26);
        big.insert(w);
    }
    auto t0 = chrono::steady_clock::now();
    int found = 0;
    for (int q = 0; q < 100000; q++)
        if (big.startsWith(string("zzz") + char('a' + q % 26))) found++;
    long long ms = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - t0).count();
    cout << found << " found, " << ms << " ms\n";
}

Node* next[26] = {} starts all 26 children as nullptr; boolalpha prints true/false instead of 1/0. The random words come from mt19937, not Java's Random, so they are different words (the count happens to come out the same). Real output (g++ -O2 -std=c++17):

true false true
true
true false false
19231 found, 1 ms

The same solution in Python

import random, time

class Node:
    __slots__ = ("next", "end")
    def __init__(self):
        self.next = {}      # letter -> child Node
        self.end = False

class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self, w):
        cur = self.root
        for ch in w:
            if ch not in cur.next:
                cur.next[ch] = Node()
            cur = cur.next[ch]
        cur.end = True

    def _walk(self, s):
        cur = self.root
        for ch in s:
            cur = cur.next.get(ch)
            if cur is None:
                return None
        return cur

    def search(self, w):
        n = self._walk(w)
        return n is not None and n.end

    def starts_with(self, p):
        return self._walk(p) is not None

t = Trie()
t.insert("apple")
print(t.search("apple"), t.search("app"), t.starts_with("app"))
t.insert("app")
print(t.search("app"))
print(t.starts_with(""), t.search("b"), t.starts_with("applesauce"))

rnd = random.Random(45)
big = Trie()
for _ in range(100000):
    big.insert("".join(chr(97 + rnd.randrange(26)) for _ in range(8)))
t0 = time.perf_counter()
found = sum(big.starts_with("zzz" + chr(97 + q % 26)) for q in range(100000))
print(found, "found,", int((time.perf_counter() - t0) * 1000), "ms")

In Python a dictionary of children (letter → Node) is the usual choice instead of a 26-slot array: it only stores the letters that exist, and it works for any character. Python prints True/False with capitals, and its random words differ from Java's, so the count differs. Real output:

True False True
True
True False False
26923 found, 52 ms

Problem 2: Word Search II (LeetCode 212, Hard)

It is like the word-search puzzles in a newspaper. You get an m × n grid of letters board and a list of words. Return every word from the list that can be traced on the grid, in any order. A word is traced by moving up, down, left or right, one square at a time, and a square can't be used twice in the same word. (Episode 35, Word Search, looked for one word.)

o a a n
e t a e
i h k r
i f l v
words Result
oath, pea, eat, rain [oath, eat]

oath is o (row 0) → a (right) → t (down) → h (down). eat is e → a → t along row 1, right to left. There is no p for pea, and the r has no a beside it for rain.

Constraints: grid up to 12 × 12, up to 30,000 words of 1 to 10 lowercase letters, all words different.

Brute force: episode 35's search, once per word

Take episode 35's DFS for one word and run it from every square, for every word in the list.

import java.util.*;

public class Main {
    static boolean dfs(char[][] b, String w, int i, int r, int c) {
        if (i == w.length()) return true;
        if (r < 0 || c < 0 || r >= b.length || c >= b[0].length
            || b[r][c] != w.charAt(i)) return false;
        char ch = b[r][c]; b[r][c] = '#';
        boolean ok = dfs(b, w, i + 1, r + 1, c) || dfs(b, w, i + 1, r - 1, c)
                  || dfs(b, w, i + 1, r, c + 1) || dfs(b, w, i + 1, r, c - 1);
        b[r][c] = ch;
        return ok;
    }
    static List<String> findWords(char[][] b, String[] words) {
        List<String> res = new ArrayList<>();
        for (String w : words) {
            boolean found = false;
            for (int r = 0; r < b.length && !found; r++)
                for (int c = 0; c < b[0].length && !found; c++)
                    if (dfs(b, w, 0, r, c)) found = true;
            if (found) res.add(w);
        }
        return res;
    }
    public static void main(String[] args) {
        char[][] b = {"oaan".toCharArray(), "etae".toCharArray(),
                      "ihkr".toCharArray(), "iflv".toCharArray()};
        System.out.println(findWords(b, new String[]{"oath", "pea", "eat", "rain"}));
    }
}

dfs returns true once i reaches the word's length; off the grid or a wrong letter is false. Otherwise it marks the square with '#', tries all four directions for the next letter, puts the letter back, and returns. Real output:

[oath, eat]

The nasty case: Time Limit Exceeded

        char[][] g = new char[12][12];
        for (char[] row : g) Arrays.fill(row, 'a');
        List<String> list = new ArrayList<>();
        for (char x = 'b'; x <= 'z'; x++)
            for (char y = 'b'; y <= 'z'; y++) list.add("aaaaaaaaaa" + x + y);
        long t0 = System.nanoTime();
        List<String> got = findWords(g, list.toArray(new String[0]));
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println(list.size() + " words, " + got.size() + " found, " + ms + " ms");

A 12 × 12 grid where every square is a, and 625 words (25 × 25): ten a's, then two other letters. None of them is on the grid, but each one only fails at its eleventh letter. In the SyntaxPilot compiler: Time Limit Exceeded (stopped after 8 s).

Why it is slow

  • For one word, the search starts from every square, and from each one it can branch 4 ways, then 3 ways at every later letter: up to 4 · 3^(L−1) paths per start.
  • On a grid of a's: 144 squares × thousands of a-a-a… paths × 625 words.
  • All 625 words walk the very same ten a's. The same work, done 625 times. It is the same waste as the list of words: shared beginnings are handled again and again.

The key insight: walk the grid and the trie together

Put all the words in one trie, then start a walk from every square and move through the trie at the same time as the grid. The trie tells us, at every step, whether any word still continues this way.

  • Start at the I (row 2, column 0). The root has no child i: no word begins with i. Stop after a single look.
  • Start at the O. The root has o. Step right to A: o has a child a. Down to T, then H. The trie has every step, and a word ends at h: oath. Found!
  • From o, a, try the next A on the right. The trie has no o-a-a. Stop at once: that whole branch is cut off. This is pruning.
  • From the E on the right: e, a, t. eat, found. pea and rain never get started.

The algorithm:

  1. Build a trie from the words; instead of a boolean end mark, store the whole word in its last node, so we can add it straight to the answer.
  2. From every square: walk(r, c, root).
  3. No child for this square's letter → return (prune).
  4. The child holds a word → add it, and set it to null so it is never added twice.
  5. Mark the square '#', walk all four directions with the child node, put the letter back.

The optimal solution in Java

import java.util.*;

public class Main {
    static class Node { Node[] next = new Node[26]; String word; }
    static List<String> findWords(char[][] b, String[] words) {
        Node root = new Node();
        for (String w : words) {
            Node cur = root;
            for (char ch : w.toCharArray()) {
                if (cur.next[ch - 'a'] == null) cur.next[ch - 'a'] = new Node();
                cur = cur.next[ch - 'a'];
            }
            cur.word = w;
        }
        List<String> res = new ArrayList<>();
        for (int r = 0; r < b.length; r++)
            for (int c = 0; c < b[0].length; c++) walk(b, r, c, root, res);
        return res;
    }
    static void walk(char[][] b, int r, int c, Node par, List<String> res) {
        if (r < 0 || c < 0 || r >= b.length || c >= b[0].length || b[r][c] == '#') return;
        char ch = b[r][c];
        Node cur = par.next[ch - 'a'];
        if (cur == null) return;
        if (cur.word != null) { res.add(cur.word); cur.word = null; }
        b[r][c] = '#';
        walk(b, r + 1, c, cur, res); walk(b, r - 1, c, cur, res);
        walk(b, r, c + 1, cur, res); walk(b, r, c - 1, cur, res);
        b[r][c] = ch;
    }
    public static void main(String[] args) {
        char[][] b = {"oaan".toCharArray(), "etae".toCharArray(),
                      "ihkr".toCharArray(), "iflv".toCharArray()};
        System.out.println(findWords(b, new String[]{"oath", "pea", "eat", "rain"}));
        System.out.println(findWords(new char[][]{{'a'}}, new String[]{"a", "b"}));
        char[][] s = {"ab".toCharArray(), "cd".toCharArray()};
        System.out.println(findWords(s, new String[]{"abdc", "abcd", "acdb", "ab"}));
    }
}

walk gets the parent trie node par: off the grid, or a square already on the path ('#'), returns; then it looks up the child for this square's letter. Real output:

[oath, eat]
[a]
[acdb, ab, abdc]

The LeetCode example; a one-square grid (a found, b not); and a 2 × 2 grid ab / cd where words bend around corners: acdb, ab and abdc are found, and abcd is correctly missing, because b and c only touch diagonally. The answer order is the order the walk finds them, which LeetCode accepts.

The nasty case in milliseconds

The grid of a's and the 625 words, with only the solver changed. Real output:

625 words, 0 found, 93 ms

Zero found, correctly, in milliseconds. The ten shared a's are walked once for all the words, and the eleventh letter is cut off at once.

The same solution in C++

#include <bits/stdc++.h>
using namespace std;

struct Node {
    Node* next[26] = {};
    string word;            // empty unless a word ends here
};

void walk(vector<string>& b, int r, int c, Node* par, vector<string>& res) {
    if (r < 0 || c < 0 || r >= (int)b.size() || c >= (int)b[0].size() || b[r][c] == '#') return;
    char ch = b[r][c];
    Node* cur = par->next[ch - 'a'];
    if (!cur) return;
    if (!cur->word.empty()) { res.push_back(cur->word); cur->word.clear(); }
    b[r][c] = '#';
    walk(b, r + 1, c, cur, res); walk(b, r - 1, c, cur, res);
    walk(b, r, c + 1, cur, res); walk(b, r, c - 1, cur, res);
    b[r][c] = ch;
}

vector<string> findWords(vector<string> b, const vector<string>& words) {
    Node* root = new Node();
    for (const string& w : words) {
        Node* cur = root;
        for (char ch : w) {
            if (!cur->next[ch - 'a']) cur->next[ch - 'a'] = new Node();
            cur = cur->next[ch - 'a'];
        }
        cur->word = w;
    }
    vector<string> res;
    for (int r = 0; r < (int)b.size(); r++)
        for (int c = 0; c < (int)b[0].size(); c++) walk(b, r, c, root, res);
    return res;
}

void print(const vector<string>& v) {
    cout << "[";
    for (size_t i = 0; i < v.size(); i++) cout << (i ? ", " : "") << v[i];
    cout << "]\n";
}

int main() {
    print(findWords({"oaan", "etae", "ihkr", "iflv"}, {"oath", "pea", "eat", "rain"}));
    print(findWords({"a"}, {"a", "b"}));
    print(findWords({"ab", "cd"}, {"abdc", "abcd", "acdb", "ab"}));

    vector<string> g(12, string(12, 'a'));
    vector<string> list;
    for (char x = 'b'; x <= 'z'; x++)
        for (char y = 'b'; y <= 'z'; y++) list.push_back(string(10, 'a') + x + y);
    auto t0 = chrono::steady_clock::now();
    vector<string> got = findWords(g, list);
    long long ms = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - t0).count();
    cout << list.size() << " words, " << got.size() << " found, " << ms << " ms\n";
}

The grid is a vector<string>, passed by value to findWords (a copy) and then by reference to walk, so the '#' marks never touch the caller's grid. An empty string plays the role of Java's null word. Real output (g++ -O2 -std=c++17):

[oath, eat]
[a]
[acdb, ab, abdc]
625 words, 0 found, 47 ms

The same solution in Python

import time

class Node:
    __slots__ = ("next", "word")
    def __init__(self):
        self.next = {}
        self.word = None    # the whole word, if one ends here

def find_words(board, words):
    b = [list(row) for row in board]          # a copy we can mark with '#'
    root = Node()
    for w in words:
        cur = root
        for ch in w:
            cur = cur.next.setdefault(ch, Node())
        cur.word = w
    res = []
    rows, cols = len(b), len(b[0])

    def walk(r, c, par):
        if r < 0 or c < 0 or r >= rows or c >= cols or b[r][c] == "#":
            return
        ch = b[r][c]
        cur = par.next.get(ch)
        if cur is None:
            return
        if cur.word is not None:
            res.append(cur.word)
            cur.word = None
        b[r][c] = "#"
        walk(r + 1, c, cur); walk(r - 1, c, cur)
        walk(r, c + 1, cur); walk(r, c - 1, cur)
        b[r][c] = ch

    for r in range(rows):
        for c in range(cols):
            walk(r, c, root)
    return res

print(find_words(["oaan", "etae", "ihkr", "iflv"], ["oath", "pea", "eat", "rain"]))
print(find_words(["a"], ["a", "b"]))
print(find_words(["ab", "cd"], ["abdc", "abcd", "acdb", "ab"]))

g = ["a" * 12] * 12
words = ["a" * 10 + x + y for x in "bcdefghijklmnopqrstuvwxyz" for y in "bcdefghijklmnopqrstuvwxyz"]
t0 = time.perf_counter()
got = find_words(g, words)
print(len(words), "words,", len(got), "found,", int((time.perf_counter() - t0) * 1000), "ms")

Python strings can't be changed in place, so the board is first copied into lists of characters. setdefault(ch, Node()) returns the existing child or stores a new one. Real output:

['oath', 'eat']
['a']
['acdb', 'ab', 'abdc']
625 words, 0 found, 2131 ms

The same answers. Python is about 20 times slower than Java here (2.1 s against 0.09 s) because every walk call is interpreted, but it is the same algorithm and still far from the brute force.

Three real bugs

Bug 1: search without the end mark

        boolean search(String w) { return walk(w) != null; }
        // main: insert("apple"), then search("app")

Real output: true. But app was never inserted! The path a-p-p exists because of apple, but no word ends there. search must check end; only startsWith may ignore it.

Bug 2: no visited mark on the path

        // walk() without  b[r][c] = '#';  and without  b[r][c] = ch;
        // main: grid {"ab"}, words {"aba"}

Real output: [aba]. But the grid has only one a! Without the '#', the walk stepped from b straight back onto the a it had already used. Mark every square on the path, and unmark it on the way back.

Bug 3: a found word that isn't cleared

        if (cur.word != null) res.add(cur.word);           // no  cur.word = null
        // main: grid {"aa"}, words {"a"}

Real output: [a, a]. The same word twice: both squares spell it. The answer must list each word once, so set the word to null as soon as it is found.

Complexity

L = length of a word or prefix, n = number of words, W = number of words in Word Search II, R × C = grid size, S = total letters of all words.

Approach insert search / startsWith Space 1 lakh words + 1 lakh checks
List of words O(1) O(n · L) O(S) TLE
Trie O(L) O(L) O(S × 26) slots 51 ms
Word Search II Time Space 12 × 12 a's, 625 words
One DFS per word O(W · R · C · 4 · 3^(L−1)) O(L) recursion TLE
One walk with a trie O(S + R · C · 4 · 3^(L−1)) O(S × 26) trie + O(L) recursion 93 ms

The trie's price is space: up to one node per stored letter, each with 26 slots. For Word Search II the worst case is still exponential in the word length L (at most 10 here), but the trie walks shared beginnings once for all words and prunes every path at the first letter no word continues with.

Common mistakes

Mistake What you see Why Fix
search returns walk(w) != null search("app") is true after only insert("apple") a prefix is not a word also check node.end
No '#' on the path [aba] on the grid ab a square was reused mark, walk, then unmark
res.add(word) only [a, a] the word was found from two squares set cur.word = null
One DFS per word Time Limit Exceeded shared prefixes walked again for every word one trie walk for all words
ch - 'a' on a capital letter: insert("Apple") java.lang.ArrayIndexOutOfBoundsException: Index -32 out of bounds for length 26 'A' - 'a' is −32 lowercase the input, or use a map of children
A list of words for startsWith Time Limit Exceeded O(n · L) per query a trie

Mini project: autocomplete for your phone

Build a small autocomplete: insert a few hundred words (for example the words of a story or a song), each with how often it appears. When the user types a prefix, walk to its node, then DFS below it to collect the words under it, and print the three most frequent suggestions (ties broken alphabetically). Read prefixes in a loop so you can type c, ca, car… and watch the suggestions narrow, just like the phone keyboard. For extra credit, store at each node its own top-3 list while inserting, so each key press costs only O(L).

Practice

  1. Add a count to each node: how many words start with p?
Solution

Every node keeps count, the number of inserted words whose path goes through it. insert adds 1 to every node on the path (the root too); countPrefix(p) walks to p's node and returns its count, or 0 if the path is missing. Both are O(L).

import java.util.*;

public class Main {
    static class Node {
        Node[] next = new Node[26];
        boolean end;
        int count;                       // how many words pass through this node
    }
    static class Trie {
        Node root = new Node();
        void insert(String w) {
            Node cur = root;
            cur.count++;
            for (char ch : w.toCharArray()) {
                int i = ch - 'a';
                if (cur.next[i] == null) cur.next[i] = new Node();
                cur = cur.next[i];
                cur.count++;
            }
            cur.end = true;
        }
        int countPrefix(String p) {
            Node cur = root;
            for (char ch : p.toCharArray()) {
                cur = cur.next[ch - 'a'];
                if (cur == null) return 0;
            }
            return cur.count;
        }
        int nodes(Node n) {
            int s = 0;
            for (Node c : n.next) if (c != null) s += 1 + nodes(c);
            return s;
        }
    }
    public static void main(String[] args) {
        Trie t = new Trie();
        for (String w : new String[]{"apple", "app", "apply", "bat"}) t.insert(w);
        System.out.println(t.countPrefix("app") + " " + t.countPrefix("appl") + " "
                + t.countPrefix("b") + " " + t.countPrefix("c") + " " + t.countPrefix(""));
        Trie q = new Trie();
        q.insert("tea"); q.insert("ten"); q.insert("to");
        System.out.println("nodes below the root: " + q.nodes(q.root));
    }
}

Real output:

3 2 1 0 4
nodes below the root: 5

app, apple, apply start with app; apple and apply with appl; only bat with b; none with c; all 4 with "". The second line checks the quiz below. (If the same word can be inserted twice, check end first and skip the counting for a repeat.)

  1. Design Add and Search Words (LeetCode 211): addWord(w), and search(w) where a . matches any one letter.
Solution

A normal trie, but search becomes a DFS: a letter follows its one child; a . tries every non-null child. At the end of the word, the node must have the end mark.

import java.util.*;

public class Main {
    static class Node { Node[] next = new Node[26]; boolean end; }
    static class WordDictionary {
        Node root = new Node();
        void addWord(String w) {
            Node cur = root;
            for (char ch : w.toCharArray()) {
                if (cur.next[ch - 'a'] == null) cur.next[ch - 'a'] = new Node();
                cur = cur.next[ch - 'a'];
            }
            cur.end = true;
        }
        boolean search(String w) { return dfs(w, 0, root); }
        boolean dfs(String w, int i, Node cur) {
            if (i == w.length()) return cur.end;
            char ch = w.charAt(i);
            if (ch == '.') {                         // try every child
                for (Node c : cur.next)
                    if (c != null && dfs(w, i + 1, c)) return true;
                return false;
            }
            Node c = cur.next[ch - 'a'];
            return c != null && dfs(w, i + 1, c);
        }
    }
    public static void main(String[] args) {
        WordDictionary d = new WordDictionary();
        d.addWord("bad"); d.addWord("dad"); d.addWord("mad");
        System.out.println(d.search("pad") + " " + d.search("bad") + " " + d.search(".ad")
                + " " + d.search("b..") + " " + d.search("..") + " " + d.search("...."));
    }
}

Real output:

false true true true false false

.. and .... are false: no stored word has 2 or 4 letters. Without dots search is O(L); each dot can multiply the work by up to 26.

  1. Replace Words (LeetCode 648): given a dictionary of roots (short words such as cat) and a sentence, replace every word that begins with a root by the shortest such root.
Solution

Put the roots in a trie. For each word of the sentence, walk the trie letter by letter and stop at the first node with the end mark: that is the shortest root. If the path breaks first, keep the word.

import java.util.*;

public class Main {
    static class Node { Node[] next = new Node[26]; boolean end; }
    static String replaceWords(List<String> dict, String sentence) {
        Node root = new Node();
        for (String w : dict) {
            Node cur = root;
            for (char ch : w.toCharArray()) {
                if (cur.next[ch - 'a'] == null) cur.next[ch - 'a'] = new Node();
                cur = cur.next[ch - 'a'];
            }
            cur.end = true;
        }
        StringBuilder out = new StringBuilder();
        for (String word : sentence.split(" ")) {
            if (out.length() > 0) out.append(' ');
            Node cur = root;
            int cut = -1;                            // length of the shortest root found
            for (int i = 0; i < word.length(); i++) {
                cur = cur.next[word.charAt(i) - 'a'];
                if (cur == null) break;
                if (cur.end) { cut = i + 1; break; }
            }
            out.append(cut == -1 ? word : word.substring(0, cut));
        }
        return out.toString();
    }
    public static void main(String[] args) {
        System.out.println(replaceWords(List.of("cat", "bat", "rat"), "the cattle was rattled by the battery"));
        System.out.println(replaceWords(List.of("a", "b", "c"), "aadsfasf absbs bbab cadsfafs"));
    }
}

Real output:

the cat was rat by the bat
a a b c

Both are the LeetCode examples. Each word costs at most its own length: O(total letters).

  1. Word Search II: remove dead trie leaves as you go.
Solution

Give each node a kids counter (how many non-null children it has). After walk returns from a node, if that node has no children left and no word waiting to be found, nothing can ever be found below it again, so cut it from its parent. Found words disappear from the trie, and later walks stop much earlier. The program below counts the calls to walk with and without this pruning, on a 12 × 12 grid of a's with the words a, aa, …, aaaaaaaaaa (all of them are on the grid).

import java.util.*;

public class Main {
    static class Node { Node[] next = new Node[26]; String word; int kids; }
    static long calls;
    static List<String> findWords(char[][] b, String[] words, boolean prune) {
        Node root = new Node();
        for (String w : words) {
            Node cur = root;
            for (char ch : w.toCharArray()) {
                if (cur.next[ch - 'a'] == null) { cur.next[ch - 'a'] = new Node(); cur.kids++; }
                cur = cur.next[ch - 'a'];
            }
            cur.word = w;
        }
        List<String> res = new ArrayList<>();
        for (int r = 0; r < b.length; r++)
            for (int c = 0; c < b[0].length; c++) walk(b, r, c, root, res, prune);
        return res;
    }
    static void walk(char[][] b, int r, int c, Node par, List<String> res, boolean prune) {
        calls++;
        if (r < 0 || c < 0 || r >= b.length || c >= b[0].length || b[r][c] == '#') return;
        char ch = b[r][c];
        Node cur = par.next[ch - 'a'];
        if (cur == null) return;
        if (cur.word != null) { res.add(cur.word); cur.word = null; }
        b[r][c] = '#';
        walk(b, r + 1, c, cur, res, prune); walk(b, r - 1, c, cur, res, prune);
        walk(b, r, c + 1, cur, res, prune); walk(b, r, c - 1, cur, res, prune);
        b[r][c] = ch;
        if (prune && cur.kids == 0 && cur.word == null) {   // a dead leaf: nothing left below it
            par.next[ch - 'a'] = null;
            par.kids--;
        }
    }
    public static void main(String[] args) {
        char[][] ex = {"oaan".toCharArray(), "etae".toCharArray(), "ihkr".toCharArray(), "iflv".toCharArray()};
        System.out.println(findWords(ex, new String[]{"oath", "pea", "eat", "rain"}, true));
        String[] as = new String[10];
        for (int k = 1; k <= 10; k++) as[k - 1] = "a".repeat(k);
        for (boolean prune : new boolean[]{false, true}) {
            char[][] g = new char[12][12];
            for (char[] row : g) Arrays.fill(row, 'a');
            calls = 0;
            List<String> got = findWords(g, as, prune);
            System.out.println("prune=" + prune + ": " + got.size() + " found, " + calls + " calls to walk");
        }
    }
}

Real output:

[oath, eat]
prune=false: 10 found, 7534800 calls to walk
prune=true: 10 found, 184 calls to walk

The same 10 words, but about 75 lakh calls drop to 184: once the first walk has found every word, the whole trie is removed and every other square stops after one look.

Quick quiz

Trie t = new Trie();
t.insert("tea");
t.insert("ten");
t.insert("to");
// nodes below the root = ?

How many nodes are there below the root: 5, 8, 6 or 7?

Answer

5. One t, shared by all three words. Under t: e and o. Under e: a and n. Eight letters were inserted, but only five nodes exist, because shared beginnings are stored once. (Practice 1 counts them: nodes below the root: 5.)

Interview questions

  1. What is a trie, and when is it better than a HashSet of words? A tree of letters where shared prefixes are stored once. A HashSet answers "is this word there?" in O(L) too, but it can't answer "does any word start with p?" without scanning every word; a trie answers it in O(L).
  2. Why does search need the end mark and startsWith not? A path can exist only because a longer word passes through it (app inside apple); the end mark says a word really ends there.
  3. 26-slot array or a hash map for the children? An array is fastest and simple for a–z but spends 26 slots per node; a map only stores the letters that exist and handles any alphabet (Unicode, capitals, digits) at some speed cost.
  4. Time and space of a trie? Each operation O(L); space up to O(total letters) nodes, each with 26 slots in the array version.
  5. Why is Word Search II faster with a trie? One walk of the grid serves all words: shared beginnings are walked once, and a path is cut as soon as no word continues with its letters.
  6. Why store the whole word in the node instead of end = true? So that when the walk reaches it we can add it to the answer directly, without carrying a StringBuilder of the path.
  7. How do you avoid duplicates in Word Search II? Set the node's word to null once it is found (or use a set). Removing dead leaves (practice 4) also stops later walks early.
  8. What if the input can contain capital letters? ch - 'a' goes negative (Index -32 out of bounds for length 26): lowercase the input first, or use a map of children.

Glossary

Term Meaning
Prefix The beginning of a word: its first few letters; "" is a prefix of every word
Trie A tree of letters where each step down is one more letter and shared beginnings are stored once
Node One box of a tree; in a trie, one letter position with its children and an end mark
Root The top node of a tree; in a trie it stands for the empty prefix
Children The nodes one step below a node
End mark (end) A flag meaning "a stored word ends at this node"
insert / search / startsWith Add a word / is this exact word stored? / does any stored word begin with this prefix?
walk (Trie) Our helper that follows a string's letters from the root and returns the node reached, or null
ch - 'a' Turns a lowercase letter into its slot number 0…25 ('c' - 'a' is 2)
null "No object here"; a null child means no word continues with that letter
ArrayList.contains / String.startsWith Check every list item for an equal one / check whether a string begins with another
Autocomplete Suggesting whole words from the letters typed so far
Grid A table of letters in rows and columns
Neighbour A square directly up, down, left or right of another (not diagonal)
DFS (depth-first search) Follow one path as deep as it goes, then come back and try the next direction
Backtracking Undoing a choice (putting the letter back) when returning from a path
Visited mark ('#') Overwriting a square while it is on the current path so it can't be reused
Pruning Cutting off a path as soon as it can't lead to an answer
Dead leaf A trie node with no children and no word left to find; safe to remove
Wildcard . In LeetCode 211, a character that matches any one letter
Root word In LeetCode 648, a short dictionary word that other words begin with
Hash map / dictionary (Python) A key → value table; here letter → child node
mt19937 C++'s standard random-number generator
O(L), O(n · L) One step per letter / every word times every letter
Exponential (3^(L−1)) Work that multiplies by a fixed factor for every extra letter
ArrayIndexOutOfBoundsException Java's error for using an array index below 0 or past the end
Lakh, crore 1 lakh = 100,000; 1 crore = 10,000,000
Time Limit Exceeded (TLE) The program was stopped for running too long (8 s in the SyntaxPilot compiler)

Summary

  • A prefix is the beginning of a word. A trie is a tree of letters: each step down is one more letter, shared beginnings are stored once, and an end mark says where a word ends.
  • A list of words costs O(n · L) per startsWith: TLE on 1 lakh words and 1 lakh checks. The trie does insert, search and startsWith in O(L): 51 ms for the same test.
  • search needs the end mark (walk(w) != null && end); startsWith only needs the node to exist.
  • Word Search II: put all the words in one trie and walk the grid and the trie together; return as soon as the trie has no child for the letter (pruning), mark squares with '#' and put them back, and clear a word once it is found. TLE → 93 ms on the grid of a's.
  • The price of a trie is space: up to one node per stored letter, each with 26 slots.

Next episode: Hashing deep dive: longest consecutive sequence, group anagrams.