INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD
01
00/15
01 / COVER MODULE 20 · TRIES
INVARIANT · MODULE 20 · TRIES
A NODE PER PREFIX, ONE WALK PER WORD

A trie keeps every prefix once, so words that start alike share a path. A question walks one path, stops at the first word on it, or searches below a node. Eleven moves, fifteen problems.

15Problems
5Families
11Units
12Live walks
← → ↑ ↓  or  W A S D  navigate SPACE next   DOUBLE-CLICK to advance I index   G goto problem   P predict H hide solutions   F fullscreen
INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
02 / INDEX PRESS I FROM ANYWHERE

INDEX — ALL 15 PROBLEMS

Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the problem's fixed number in this deck, not a slide position.

WALK ONE PATH · 04
SEARCH BELOW A NODE · 03
THE TRIE INSIDE ANOTHER SEARCH · 04
A TRIE NEVER BUILT · 02
A TRIE OF BITS · 02
SOLVED HAS A JUDGE LINK
INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
03 / MECHANISM UNIT 01 · INSERT

A NODE PER LETTER, A RING AT THE END

A word walks down from the root and grows a node for each missing letter. Its last node gets a ring.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
04 / MECHANISM UNIT 01 · SEARCH

ONE WALK, TWO QUESTIONS

search and startsWith walk the string down the same way. search also needs a ring where the walk stops.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
05 / DRILL UNIT 01 · A Node per Prefix · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

insert("apple"), then insert("app"). How many nodes are below the root?

"apple" grows a, p, p, l, e. "app" walks a, p, p and grows nothing; it only rings the second p.

DRILL 02 · TRACE

In that trie: search("ap") and startsWith("ap")?

The walk reaches the first p in both. It has no ring, so search is false.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
06 / PROBLEM #01 · WALK · MED

Implement Trie (Prefix Tree)

MED walk ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Build a structure with insert, search for a whole word, and startsWith for a prefix.

INTUITION

Every prefix of every word gets one node, and a letter is an edge from a prefix to the prefix one letter longer. Inserting walks down from the root and makes the nodes that are missing. Both queries walk the same way and fail at a missing child. search also needs a word to end at the last node, which a flag on that node records; startsWith only needs the node to exist.

STEPS
  1. Each node keeps 26 children and a flag for a word ending there
  2. insert walks the letters, making a child when it is missing, and sets the flag
  3. search walks and returns whether the last node has the flag
  4. startsWith walks and returns whether it got to the end
↕ SCROLL
class Trie {
    struct Node {
        Node* next[26] = {};
        bool end = false;                      // a word ends here
    };
    Node* root = new Node();
    Node* walk(const string& s) {              // the node for s, or null
        Node* cur = root;
        for (char ch : s) {
            cur = cur->next[ch - 'a'];
            if (!cur) return nullptr;
        }
        return cur;
    }
public:
    void insert(string word) {
        Node* cur = root;
        for (char ch : word) {
            Node*& nx = cur->next[ch - 'a'];
            if (!nx) nx = new Node();          // a new prefix
            cur = nx;
        }
        cur->end = true;
    }
    bool search(string word) {
        Node* n = walk(word);
        return n && n->end;
    }
    bool startsWith(string prefix) { return walk(prefix) != nullptr; }
};
TIMEO(L) per callone step per letter
SPACEO(total letters)one node per new prefix
TRAP

A search that only walks. After insert("apple"), search("app") walks to a node that exists, but no word ends there. Returning true because the walk succeeded answers startsWith, not search.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
07 / PROBLEM #02 · WALK · MED

Find the Length of the Longest Common Prefix

MED walk ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Two arrays of positive integers. Find the longest common prefix of digits over every pair (x from arr1, y from arr2).

INTUITION

Comparing every pair costs up to 2.5 × 10⁹ comparisons. Put the digits of every x from arr1 into a trie instead, one digit per edge. A number y from arr2 then walks down the trie digit by digit, and the depth where its path stops is its longest prefix shared with any x. The answer is the deepest such walk.

STEPS
  1. Insert the digit string of every number in arr1
  2. Walk each number of arr2 down the trie until a digit has no child
  3. The number of digits walked is its best prefix; keep the largest
BRUTEO(m · n · 9)
→
OPTIMALO((m + n) · 9)
↕ SCROLL
int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
    vector<array<int, 10>> next(1);            // node 0 is the root; 0 = no child
    for (int x : arr1) {
        int cur = 0;
        for (char ch : to_string(x)) {
            int d = ch - '0';
            if (!next[cur][d]) {
                next[cur][d] = next.size();
                next.push_back({});
            }
            cur = next[cur][d];
        }
    }
    int best = 0;
    for (int y : arr2) {
        int cur = 0, len = 0;
        for (char ch : to_string(y)) {
            int d = ch - '0';
            if (!next[cur][d]) break;          // the paths part here
            cur = next[cur][d];
            len++;
        }
        best = max(best, len);
    }
    return best;
}
TIMEO((m + n) · 9)each number has at most 9 digits
SPACEO(9m)a trie of arr1's digits
TRAP

Keeping the last walk, not the best. Writing best = len after each y returns the prefix of the last number in arr2. With arr1 = [100] and arr2 = [1000, 2], that is 0 instead of 3.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
08 / DRILL UNIT 01 · A Node per Prefix · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

longestCommonPrefix([12, 125, 31], [1256, 315, 4])?

1256 walks 1, 2, 5 and finds no 6. 315 walks 3, 1, and 4 has no edge at all.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
09 / MECHANISM UNIT 02 · STOP AT THE FIRST WORD

STOP AT THE FIRST RING

Each word walks down the trie of roots. The first ring it meets is the shortest root that starts it.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
10 / DRILL UNIT 02 · Stop at the First Word · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

replaceWords(["a", "aa", "aaa"], "aaaa bbb")?

aaaa meets the ring on a first. bbb falls off at once and stays.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
11 / PROBLEM #03 · WALK · MED

Replace Words

MED walk ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Replace each word of a sentence by the shortest root from a dictionary that starts it, if any does.

INTUITION

Put the roots in a trie. A word of the sentence walks down from the root, letter by letter, and the first node where a root ends is the shortest root that starts the word, so the walk stops there. If the walk falls off the trie or reaches the end of the word first, no root fits and the word stays.

STEPS
  1. Insert every root, marking the node where it ends
  2. Walk each word of the sentence down the trie
  3. Stop at the first marked node and write the letters walked
  4. If the walk ends without one, write the word as it is
↕ SCROLL
string replaceWords(vector<string>& dictionary, string sentence) {
    vector<array<int, 26>> next(1);
    vector<bool> end(1, false);
    for (auto& w : dictionary) {
        int cur = 0;
        for (char ch : w) {
            int c = ch - 'a';
            if (!next[cur][c]) {
                next[cur][c] = next.size();
                next.push_back({});
                end.push_back(false);
            }
            cur = next[cur][c];
        }
        end[cur] = true;
    }
    stringstream in(sentence);
    string word, out;
    while (in >> word) {
        int cur = 0, len = 0;
        for (char ch : word) {
            cur = next[cur][ch - 'a'];
            if (!cur) break;                   // no root fits
            len++;
            if (end[cur]) break;               // the shortest root
        }
        if (!out.empty()) out += ' ';
        out += (cur && end[cur]) ? word.substr(0, len) : word;
    }
    return out;
}
TIMEO(D + S)each letter is walked at most once
SPACEO(D)a trie of the roots
TRAP

Walking on past the first root. With roots a, aa and aaa, the word aaaa must become a. A walk that keeps going and remembers the last root it passed writes aaa, the longest root instead of the shortest.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
12 / PROBLEM #04 · WALK · MED

Remove Sub-Folders from the Filesystem

MED walk ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

A list of folder paths. Remove every sub-folder, a path that starts with another path followed by "/".

INTUITION

Split each path at "/" and insert its parts into a trie, one part per edge, marking the node where a folder ends. A folder is a sub-folder exactly when a marked node sits above it. So walk the trie from the root and stop going down at the first marked node on each path: that folder is kept, and everything below it is a sub-folder.

STEPS
  1. Insert each folder's parts, recording the folder at its last node
  2. Walk the trie from the root with a stack
  3. At a node where a folder ends, keep that folder and go no deeper
  4. Otherwise push its children
↕ SCROLL
vector<string> removeSubfolders(vector<string>& folder) {
    vector<map<string, int>> next(1);          // part -> child
    vector<int> end(1, -1);                    // the folder that ends here, or -1
    for (int i = 0; i < (int)folder.size(); i++) {
        stringstream ss(folder[i].substr(1));
        string part;
        int cur = 0;
        while (getline(ss, part, '/')) {
            if (!next[cur].count(part)) {
                int id = next.size();
                next[cur][part] = id;
                next.emplace_back();
                end.push_back(-1);
            }
            cur = next[cur][part];
        }
        end[cur] = i;
    }
    vector<string> out;
    vector<int> st = {0};
    while (!st.empty()) {
        int u = st.back(); st.pop_back();
        if (end[u] >= 0) {                     // everything below is a sub-folder
            out.push_back(folder[end[u]]);
            continue;
        }
        for (auto& kv : next[u]) st.push_back(kv.second);
    }
    return out;
}
TIMEO(total length)each part is inserted and visited once
SPACEO(total length)a trie of path parts
TRAP

A trie of characters. Inserted letter by letter, "/a/b" is a prefix of "/a/bc", so "/a/bc" is dropped as its sub-folder. It is not one: a sub-folder must continue with "/". Splitting at "/" makes "b" and "bc" different edges.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
13 / DRILL UNIT 02 · Stop at the First Word · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

removeSubfolders(["/a", "/a/b", "/ab", "/c/d", "/c"])?

/a/b sits under /a and /c/d under /c. "ab" is its own part, so /ab stays.

DRILL 02 · RECALL

Why split the paths at "/" instead of inserting letters?

A sub-folder continues with "/". As parts, b and bc are different edges.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
14 / MECHANISM UNIT 03 · ONLY THROUGH WORDS

ONLY THROUGH WORDS

The search steps only into nodes with a ring, so every prefix on its path is a word. Children go a to z, so a tie keeps the smaller word.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
15 / DRILL UNIT 03 · Only Through Words

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

longestWord(["b", "ba", "bat", "c", "ca", "cat"])?

Both can be built and both have three letters. The search visits b first, and only a longer word replaces best.

DRILL 02 · RECALL

With "banana" and "a" in the list but not "b", why is banana never reached?

The search steps only into nodes with a ring. Without "b", nothing below b is a word built one letter at a time.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
16 / PROBLEM #05 · SEARCH · MED

Longest Word in Dictionary

MED search ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Find the longest word that can be built one letter at a time, each step being a word in the list. Break ties by the smallest word.

INTUITION

A word can be built that way exactly when every prefix of it is in the list, which in a trie means every node on its path is marked as a word's end. So search the trie from the root and only step into children that are marked. The deepest node reached is the longest buildable word, and visiting children from a to z keeps the smallest one when depths tie.

STEPS
  1. Insert every word, marking its last node
  2. Search from the root, stepping only into marked children, a to z
  3. Keep a path when it is longer than the best, or as long and smaller
↕ SCROLL
string longestWord(vector<string>& words) {
    vector<array<int, 26>> next(1);
    vector<bool> end(1, true);                 // the root: the empty word
    for (auto& w : words) {
        int cur = 0;
        for (char ch : w) {
            int c = ch - 'a';
            if (!next[cur][c]) {
                next[cur][c] = next.size();
                next.push_back({});
                end.push_back(false);
            }
            cur = next[cur][c];
        }
        end[cur] = true;
    }
    string best, path;
    function<void(int)> dfs = [&](int u) {     // only words lead further down
        if (path.size() > best.size()) best = path;
        for (int c = 0; c < 26; c++) {
            int v = next[u][c];
            if (!v || !end[v]) continue;
            path.push_back('a' + c);
            dfs(v);
            path.pop_back();
        }
    };
    dfs(0);
    return best;
}
TIMEO(total letters)each node is visited at most once
SPACEO(total letters)the trie and the search stack
TRAP

Checking only the word's own end. "banana" is in the list, but "b" is not, so it cannot be built. A search that steps into any child finds banana, six letters, and returns it over "apple", which can be built.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
17 / MECHANISM UNIT 04 · THREE WORDS AT EVERY NODE

THE FIRST THREE THAT PASS

Products go in sorted, and each node keeps the first three that pass it. Typing walks one node per letter and reads its list.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
18 / DRILL UNIT 04 · Three Words at Every Node

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Products mobile, mouse, moneypot, monitor, mousepad. The list after typing "mou"?

Only two products start with "mou". Sorted, mouse comes before mousepad.

DRILL 02 · RECALL

Why may a node keep only the first three products that reach it?

Products go in letter order, so a later one with the same prefix is never smaller.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
19 / PROBLEM #06 · SEARCH · MED

Search Suggestions System

MED search ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

After each letter of searchWord is typed, suggest the three smallest products that start with what has been typed.

INTUITION

Sort the products first. Inserting them in that order, each node on a product's path is a prefix of it, so a node can keep the first three products that pass through it, and those are the three smallest with that prefix. Typing then walks down one node per letter and reads the list stored there. Once a letter has no child, every later prefix has no products either.

STEPS
  1. Sort the products
  2. Insert them in order; each node on the path keeps the product if it holds fewer than 3
  3. Walk searchWord one letter at a time and read each node's list
  4. After the walk falls off the trie, every list is empty
↕ SCROLL
vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
    sort(products.begin(), products.end());    // smallest first
    vector<array<int, 26>> next(1);
    vector<vector<int>> top(1);                // node -> the first 3 products through it
    for (int i = 0; i < (int)products.size(); i++) {
        int cur = 0;
        for (char ch : products[i]) {
            int c = ch - 'a';
            if (!next[cur][c]) {
                next[cur][c] = next.size();
                next.push_back({});
                top.emplace_back();
            }
            cur = next[cur][c];
            if (top[cur].size() < 3) top[cur].push_back(i);
        }
    }
    vector<vector<string>> out;
    int cur = 0;                               // -1 once off the trie
    for (char ch : searchWord) {
        if (cur != -1) cur = next[cur][ch - 'a'] ? next[cur][ch - 'a'] : -1;
        out.emplace_back();
        if (cur != -1)
            for (int i : top[cur]) out.back().push_back(products[i]);
    }
    return out;
}
TIMEO(L log n + total letters)the sort, then one step per letter
SPACEO(total letters)up to three indices per node
TRAP

Inserting before sorting. Each node keeps the first three products to reach it. Unsorted, those are the first three in the input, not the smallest: with products ["mouse", "mobile", "moneypot", "monitor"], the list at "mo" starts with mouse.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
20 / MECHANISM UNIT 05 · A DOT TRIES EVERY CHILD

A DOT TRIES EVERY CHILD

A letter follows one edge. A dot tries each child in turn until one of them reaches a word.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
21 / DRILL UNIT 05 · A Dot Tries Every Child · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

addWord bad, dad, mad. Then search("pad"), search(".ad"), search("b..")?

No word starts with p. The dot finds bad first, and b.. reaches the ring on bad's d.

DRILL 02 · TRACE

Only "bad" is stored. search("b.")?

The walk reaches ba, but no word ends there.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
22 / DRILL UNIT 05 · A Dot Tries Every Child · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Why does a search with dots stay fast here?

Each dot branches at most 26 ways and the rest of the pattern is one path.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
23 / PROBLEM #07 · SEARCH · MED

Design Add and Search Words Data Structure

MED search ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

addWord stores a word, and search asks whether any stored word matches a pattern in which "." stands for any letter.

INTUITION

Store the words in a trie. A pattern of letters walks one path, but a dot can be any letter, so at a dot the search tries every child and succeeds if any of them leads to a match. That is a depth-first search over the trie that branches only at dots. With at most two dots per pattern, the branching stays small.

STEPS
  1. addWord inserts the word and marks its last node
  2. search matches from the root, one pattern letter per level
  3. A letter follows its one child, failing if it is missing
  4. A dot tries every child; at the end of the pattern the node must be marked
↕ SCROLL
class WordDictionary {
    struct Node {
        Node* next[26] = {};
        bool end = false;
    };
    Node* root = new Node();
    bool match(Node* u, const string& w, int i) {
        if (i == (int)w.size()) return u->end;
        if (w[i] != '.') {
            Node* v = u->next[w[i] - 'a'];
            return v && match(v, w, i + 1);
        }
        for (Node* v : u->next)                // a dot: try every child
            if (v && match(v, w, i + 1)) return true;
        return false;
    }
public:
    void addWord(string word) {
        Node* cur = root;
        for (char ch : word) {
            Node*& nx = cur->next[ch - 'a'];
            if (!nx) nx = new Node();
            cur = nx;
        }
        cur->end = true;
    }
    bool search(string word) { return match(root, word, 0); }
};
TIMEO(L) per add, O(26² · L) per searchtwo dots branch at most 26 ways each
SPACEO(total letters)the trie and the recursion
TRAP

A match that ends anywhere. With "bad" stored, search("b.") reaches the node for "ba". Returning true there accepts a prefix. The pattern matches only if a word ends at that node, so the answer is false.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
24 / MECHANISM UNIT 06 · THE BOARD AND THE TRIE TOGETHER

THE TRIE STEERS THE SEARCH

One search from each cell carries a trie node and steps only to letters that are its children. A node with nothing left below it is cut.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
25 / DRILL UNIT 06 · The Board and the Trie Together · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Board [[a, b], [c, d]], words abcb, abdc, acdb?

b and c are not next to each other. a-b-d-c and a-c-d-b both are.

DRILL 02 · RECALL

Why clear a word from its node once it is found?

Two paths can spell the same word, and the answer lists each word once.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
26 / DRILL UNIT 06 · The Board and the Trie Together · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Why put the letter back after the neighbours are searched?

# only means "on this path". Once the search leaves, the cell is free.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
27 / PROBLEM #08 · COMBINE · HARD

Word Search II

HARD combine ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

A board of letters and a list of words. Return every word that can be traced on the board through adjacent cells, each cell used at most once in a word.

INTUITION

Searching the board once per word repeats the same paths for words that share a prefix. Put the words in a trie and run one depth-first search from each cell, carrying the trie node along. A step onto a cell is taken only if its letter is a child of the current node, so the search stops as soon as no word continues that way. A word found is removed from its node, and a node left with nothing below it is cut off, so dead branches are not searched again.

STEPS
  1. Insert every word, storing it at its last node
  2. From each cell, step to a neighbour only if its letter is a child of the node
  3. Mark the cell used while below it, and unmark it on the way back
  4. Collect and remove a word on reaching its node; cut a node that is left empty
BRUTEO(W · m · n · 4 · 3^(L−1))
→
OPTIMALO(m · n · 4 · 3^(L−1))
↕ SCROLL
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
    struct Node { Node* next[26] = {}; int word = -1, kids = 0; };
    Node* root = new Node();
    for (int i = 0; i < (int)words.size(); i++) {
        Node* cur = root;
        for (char ch : words[i]) {
            Node*& nx = cur->next[ch - 'a'];
            if (!nx) { nx = new Node(); cur->kids++; }
            cur = nx;
        }
        cur->word = i;
    }
    int m = board.size(), n = board[0].size();
    vector<string> out;
    function<void(int, int, Node*)> dfs = [&](int r, int c, Node* parent) {
        char ch = board[r][c];
        Node* u = parent->next[ch - 'a'];
        if (u->word >= 0) { out.push_back(words[u->word]); u->word = -1; }   // once each
        board[r][c] = '#';                     // used on this path
        int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1};
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n || board[nr][nc] == '#') continue;
            if (u->next[board[nr][nc] - 'a']) dfs(nr, nc, u);
        }
        board[r][c] = ch;
        if (u->word < 0 && u->kids == 0) {     // nothing left below: cut it off
            parent->next[ch - 'a'] = nullptr;
            parent->kids--;
        }
    };
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++)
            if (root->next[board[r][c] - 'a']) dfs(r, c, root);
    return out;
}
TIMEO(m · n · 4 · 3^(L−1))each start explores paths up to the longest word
SPACEO(total letters)the trie, plus a path of at most 10 cells
TRAP

Finding a word twice. On a board where "eat" can be traced from two places, the search reaches its node twice and reports it twice. Removing the word from its node the first time keeps each word in the answer once.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
28 / MECHANISM UNIT 07 · EVERY WORD THAT STARTS HERE

EVERY WORD THAT STARTS AT i

dp[i] counts the ways to build s[i..]. The walk from i finds each word s[i..j], and each adds dp[j + 1].

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
29 / DRILL UNIT 07 · Every Word That Starts Here

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

s = "aaa", words a and aa. In how many ways can s be built?

a + a + a, a + aa and aa + a.

DRILL 02 · RECALL

Why walk the trie from i rather than test every s[i..j] in a set?

Testing each s[i..j] costs n² lookups, each hashing up to n letters. The walk ends at the first missing edge.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
30 / PROBLEM #09 · COMBINE · MED

Word Combinations

MED combine ▶ SOLVE ON CSESCSES does not rate its problems; the chip is this deck's estimate. Submit the Python tab as PyPy3.
SIGNAL — WHAT GIVES IT AWAY

A string and a dictionary. Count the ways to build the string by joining dictionary words, modulo 10⁹ + 7.

INTUITION

Let dp[i] be the number of ways to build the suffix that starts at i, with dp[n] = 1 for the empty suffix. A way to build it starts with some word that matches s from i, and continues with a way to build what is left. To find those words, walk the trie from the root along s[i], s[i + 1], and so on: every marked node on the walk is a word ending at j, which adds dp[j + 1]. The walk stops when the trie has no child for the next letter, so it never passes the longest word.

STEPS
  1. Insert every dictionary word into a trie
  2. Fill dp from i = n − 1 down to 0, with dp[n] = 1
  3. From i, walk the trie along s; at each marked node ending at j, add dp[j + 1]
  4. Print dp[0]
BRUTEO(n² · L) with a hash set of words
→
OPTIMALO(n · min(n, longest word) + total)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    int k;
    cin >> s >> k;
    vector<array<int, 26>> next(1);
    vector<bool> end(1, false);
    for (int i = 0; i < k; i++) {
        string w;
        cin >> w;
        int cur = 0;
        for (char ch : w) {
            int c = ch - 'a';
            if (!next[cur][c]) {
                next[cur][c] = next.size();
                next.push_back({});
                end.push_back(false);
            }
            cur = next[cur][c];
        }
        end[cur] = true;
    }
    const long long MOD = 1000000007;
    int n = s.size();
    vector<long long> dp(n + 1, 0);            // dp[i]: ways to build s[i..]
    dp[n] = 1;
    for (int i = n - 1; i >= 0; i--) {
        int cur = 0;
        for (int j = i; j < n; j++) {          // every word that starts at i
            cur = next[cur][s[j] - 'a'];
            if (!cur) break;
            if (end[cur]) dp[i] = (dp[i] + dp[j + 1]) % MOD;
        }
    }
    cout << dp[0] << "\n";
}
TIMEO(n · min(n, longest word) + total)each start walks at most the longest word
SPACEO(total letters + n)the trie and the dp array
TRAP

Stopping at the first word. From i = 0 in "ababc", both ab and abab match. A walk that stops at the first marked node counts only ab + ab + c and prints 1. The walk must carry on past a word to find the longer ones.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
31 / MECHANISM UNIT 08 · READ THE WORDS BACKWARDS

READ THE STREAM BACKWARDS

The words go in reversed. A query walks back from the newest letter, so every suffix shares one walk.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
32 / DRILL UNIT 08 · Read the Words Backwards · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Words cd, f, kl. The stream a, b, c, d: the four answers?

Only after d does a word end at the newest letter: cd.

DRILL 02 · RECALL

Why insert the words reversed?

One walk back from the newest letter passes every suffix's start at once.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
33 / PROBLEM #10 · COMBINE · HARD

Stream of Characters

HARD combine ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Letters arrive one at a time. After each, say whether some suffix of the stream is a word from the list.

INTUITION

A suffix ends at the newest letter, so it is read from the newest letter backwards. Insert every word reversed into a trie. After each letter, walk the trie from the newest letter back through the stream: reaching a marked node means the letters walked, read forwards, are a word. The walk stops at a missing child or after as many letters as the longest word.

STEPS
  1. Insert every word reversed, marking the node where it ends
  2. Keep the stream's letters in order
  3. On a query, walk the trie from the newest letter backwards
  4. Return true at the first marked node, false when the walk stops
↕ SCROLL
class StreamChecker {
    vector<array<int, 26>> next;
    vector<bool> end;
    string seen;                               // the letters so far
    int longest = 0;
public:
    StreamChecker(vector<string>& words) : next(1), end(1, false) {
        for (auto& w : words) {
            int cur = 0;
            for (int i = (int)w.size() - 1; i >= 0; i--) {   // each word reversed
                int c = w[i] - 'a';
                if (!next[cur][c]) {
                    next[cur][c] = next.size();
                    next.push_back({});
                    end.push_back(false);
                }
                cur = next[cur][c];
            }
            end[cur] = true;
            longest = max(longest, (int)w.size());
        }
    }
    bool query(char letter) {
        seen.push_back(letter);
        int cur = 0, n = seen.size();
        for (int i = n - 1; i >= 0 && i >= n - longest; i--) {
            cur = next[cur][seen[i] - 'a'];
            if (!cur) return false;            // no word ends this way
            if (end[cur]) return true;
        }
        return false;
    }
};
TIMEO(longest word) per querya walk back of at most 200 letters
SPACEO(total letters + queries)the reversed trie and the stream
TRAP

A trie of the words as written. Walking forwards from each earlier letter finds the same answers, but each query then walks from up to 200 starting points. Reversed, every suffix starts at the newest letter, so one walk covers them all.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
34 / PROBLEM #11 · COMBINE · HARD

Palindrome Pairs

HARD combine ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Unique words. Find every pair (i, j), i ≠ j, whose concatenation words[i] + words[j] is a palindrome.

INTUITION

words[i] + words[j] reads the same both ways in two shapes. If words[i] is the longer, it starts with the reverse of words[j] and the rest of it is a palindrome. If words[j] is the longer, its reverse starts with words[i] and the rest of that reverse is a palindrome. Insert every word reversed into a trie. A node where a reverse ends records its word, and each node also lists the words whose reverse goes on below it as a palindrome. Walking words[i] down the trie finds the first shape at every recorded node it passes, and the second shape in the list at its last node.

STEPS
  1. Insert each word reversed; at each node, list the word if what is left of the reverse is a palindrome
  2. Walk each word down the trie letter by letter
  3. At a node where another word's reverse ends, pair them if the rest of the walking word is a palindrome
  4. After the whole word, pair it with every other word in the last node's list
BRUTEO(n² · L)
→
OPTIMALO(n · L²)
↕ SCROLL
vector<vector<int>> palindromePairs(vector<string>& words) {
    auto pal = [](const string& s, int i, int j) {   // s[i..j] reads the same both ways
        while (i < j) if (s[i++] != s[j--]) return false;
        return true;
    };
    vector<array<int, 26>> next(1);
    vector<int> word(1, -1);                   // the word whose reverse ends here
    vector<vector<int>> rest(1);               // words whose reverse goes on as a palindrome
    for (int j = 0; j < (int)words.size(); j++) {
        const string& w = words[j];
        int cur = 0;
        for (int i = (int)w.size() - 1; i >= 0; i--) {   // w reversed
            if (pal(w, 0, i)) rest[cur].push_back(j);    // what is left reads the same
            int c = w[i] - 'a';
            if (!next[cur][c]) {
                next[cur][c] = next.size();
                next.push_back({});
                word.push_back(-1);
                rest.emplace_back();
            }
            cur = next[cur][c];
        }
        word[cur] = j;
        rest[cur].push_back(j);                // nothing left: that reads the same too
    }
    vector<vector<int>> out;
    for (int i = 0; i < (int)words.size(); i++) {
        const string& w = words[i];
        int cur = 0, n = w.size();
        for (int k = 0; k < n && cur != -1; k++) {
            if (word[cur] >= 0 && word[cur] != i && pal(w, k, n - 1))
                out.push_back({i, word[cur]});     // w = reverse(other) + palindrome
            cur = next[cur][w[k] - 'a'] ? next[cur][w[k] - 'a'] : -1;
        }
        if (cur != -1)
            for (int j : rest[cur])
                if (j != i) out.push_back({i, j});     // reverse(other) = w + palindrome
    }
    return out;
}
TIMEO(n · L²)a palindrome check of up to L letters at each of L positions
SPACEO(n · L)the reversed trie and its lists
TRAP

Only exact reverses. Matching each word against the reverses of the others finds ("abcd", "dcba") but misses ("lls", "sssll"): the reverse of sssll is llsss, which starts with lls and goes on as sss, a palindrome. That case lives in the node lists.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
35 / DRILL UNIT 08 · Read the Words Backwards · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

palindromePairs(["abcd", "dcba", "lls", "s", "sssll"]): how many pairs?

(0, 1) and (1, 0), then s + lls = slls and lls + sssll = llssssll.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
36 / MECHANISM UNIT 09 · COUNT A SUBTREE WITHOUT BUILDING IT

COUNT A SUBTREE, LEVEL BY LEVEL

The numbers 1 to n form a trie of digits. Counting the numbers under cur says whether to skip its subtree or go down into it.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
37 / DRILL UNIT 09 · Count a Subtree Without Building It · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

The first six numbers of lexicalOrder(13)?

Dictionary order is the digit trie in preorder: 1, then its children 10 to 13, then 2.

DRILL 02 · TRACE

findKthNumber(13, 2)?

count(1) = 5 is more than k = 1, so the walk goes down from 1 to 10.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
38 / DRILL UNIT 09 · Count a Subtree Without Building It · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

In count(p), why does each level stop at min(n, hi)?

Under 2 with n = 21, the level 20 to 29 holds only 20 and 21.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
39 / PROBLEM #12 · IMPLICIT · MED

Lexicographical Numbers

MED implicit ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

List the numbers 1 to n in dictionary order, in O(n) time and O(1) extra space.

INTUITION

The numbers 1 to n are the nodes of a trie of digits, with 1 to 9 under the root and d·10 to d·10 + 9 under d. Dictionary order is that trie read in preorder, and the trie never needs building, since each move is arithmetic. From cur, go down to cur · 10 if it is at most n. Otherwise go to the next sibling, cur + 1, first climbing (cur / 10) while cur ends in 9 or cur + 1 is past n.

STEPS
  1. Start at cur = 1 and write n numbers
  2. Go down to cur × 10 when it is at most n
  3. Otherwise climb while cur ends in 9 or cur + 1 > n, then add 1
↕ SCROLL
vector<int> lexicalOrder(int n) {
    vector<int> out;
    int cur = 1;
    for (int i = 0; i < n; i++) {
        out.push_back(cur);
        if (cur * 10 <= n) cur *= 10;          // down to the first child
        else {
            while (cur % 10 == 9 || cur + 1 > n) cur /= 10;   // no next sibling: climb
            cur++;
        }
    }
    return out;
}
TIMEO(n)each number is written once; the climbs total O(n)
SPACEO(1)beyond the output
TRAP

Climbing only past n. With n = 25, after 19 comes 2. A loop that climbs only when cur + 1 > n goes from 19 to 20, which is 19's sibling in counting but not in the trie: 20 belongs under 2.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
40 / PROBLEM #13 · IMPLICIT · HARD

K-th Smallest in Lexicographical Order

HARD implicit ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Return the k-th number in dictionary order among 1 to n, for n up to 10⁹.

INTUITION

The same digit trie, but n is too large to walk it number by number. What helps is counting how many of 1 to n lie below a prefix p without listing them. Level by level the subtree of p covers [p, p], then [10p, 10p + 9], then [100p, 100p + 99], and each range is cut at n. If that count is at most the numbers still to skip, the whole subtree is skipped and p moves to its sibling. Otherwise the answer is inside, so step down to 10p, which uses up one number.

STEPS
  1. Start at cur = 1 with k − 1 numbers left to skip
  2. Count the numbers under cur, level by level, cut at n
  3. If the count is at most k, skip them all and move to cur + 1
  4. Otherwise step down to cur × 10 and skip one
BRUTEO(n log n), sorting 1..n as strings
→
OPTIMALO(log² n)
↕ SCROLL
int findKthNumber(int n, int k) {
    auto count = [&](long long p) {            // how many of 1..n start with p
        long long cnt = 0, lo = p, hi = p;
        while (lo <= n) {
            cnt += min<long long>(n, hi) - lo + 1;
            lo *= 10;
            hi = hi * 10 + 9;
        }
        return cnt;
    };
    long long cur = 1;
    k -= 1;                                    // cur = 1 is the first number
    while (k > 0) {
        long long c = count(cur);
        if (c <= k) { k -= c; cur++; }         // skip the whole subtree
        else { k -= 1; cur *= 10; }            // the answer is inside: go down
    }
    return (int)cur;
}
TIMEO(log² n)at most 10 steps per digit, each counting over 10 levels
SPACEO(1)a few counters
TRAP

Ranges in 32 bits. With n = 10⁹ the count's lo and hi reach 10¹⁰ before the loop stops, past 2³¹. In C++ and Java they must be 64-bit, or the count wraps and the walk skips the wrong subtree.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
41 / MECHANISM UNIT 10 · BITS AS A PATH

TAKE THE OPPOSITE BIT

Numbers are paths of bits, high bit first. The walk takes the bit opposite to x's wherever it can, and sorting the queries by m lets only a ≤ m in.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
42 / DRILL UNIT 10 · Bits as a Path

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

maximizeXor([0, 1, 2, 3, 4], [[3, 1], [1, 3], [5, 6]])?

3 XOR 0, 1 XOR 2 and 5 XOR 2.

DRILL 02 · RECALL

Why take the opposite bit at the highest bit first?

2ᵇ is more than 2ᵇ − 1, the most that every lower bit can add.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
43 / PROBLEM #14 · BITS · HARD

Maximum XOR With an Element From Array

HARD bits ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

For each query (x, m), find the largest x XOR a over the numbers a in nums with a ≤ m, or −1 if there are none.

INTUITION

Written in 30 bits from the top, numbers form a binary trie. To make x XOR a large, a should differ from x in the highest bits first, so walk down choosing the opposite of x's bit whenever that child exists. The limit a ≤ m is handled offline. Sort nums and the queries by m, and before each query insert every number that is now at most m. The trie then holds exactly the allowed numbers.

STEPS
  1. Sort nums, and the queries by m
  2. Before each query, insert the numbers ≤ m from the top bit down
  3. If none are in yet, the answer is −1
  4. Otherwise walk down, taking the opposite bit when it exists and setting that bit of the answer
BRUTEO(n · q)
→
OPTIMALO((n + q) · 30 + q log q)
↕ SCROLL
vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
    sort(nums.begin(), nums.end());
    vector<int> order(queries.size());
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(),
         [&](int a, int b) { return queries[a][1] < queries[b][1]; });
    vector<array<int, 2>> next(1, {{0, 0}});
    vector<int> ans(queries.size());
    size_t j = 0;
    for (int q : order) {
        int x = queries[q][0], m = queries[q][1];
        for (; j < nums.size() && nums[j] <= m; j++) {   // every num <= m goes in
            int cur = 0;
            for (int b = 29; b >= 0; b--) {
                int bit = nums[j] >> b & 1;
                if (!next[cur][bit]) {
                    next[cur][bit] = next.size();
                    next.push_back({{0, 0}});
                }
                cur = next[cur][bit];
            }
        }
        if (j == 0) { ans[q] = -1; continue; } // nothing is small enough
        int cur = 0, best = 0;
        for (int b = 29; b >= 0; b--) {
            int want = (x >> b & 1) ^ 1;       // the opposite bit sets this one
            if (next[cur][want]) { best |= 1 << b; cur = next[cur][want]; }
            else cur = next[cur][want ^ 1];
        }
        ans[q] = best;
    }
    return ans;
}
TIMEO((n + q) · 30 + q log q)30 bits per insert and per query
SPACEO(30n)the binary trie
TRAP

Inserting a < m. The limit is a ≤ m. With nums = [5] and the query (2, 5), a strict test leaves the trie empty and returns −1, when 5 is allowed and 2 XOR 5 = 7.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
44 / MECHANISM UNIT 11 · COUNTS LET A TRIE FORGET

COUNTS, NOT DELETIONS

Each node counts the numbers that pass through it. − x lowers the counts, and a query treats a count of 0 as no child.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
45 / DRILL UNIT 11 · Counts Let a Trie Forget

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

From {0}: + 8, + 9, + 11, + 6, + 1, then ? 3?

3 XOR 8 = 11 is the largest. The sample's next answers are 10, 14 and 13.

DRILL 02 · RECALL

Why keep a count per node instead of deleting nodes on "−"?

8 and 9 share every node but the last. Removing 8 must leave 9's path whole.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
46 / PROBLEM #15 · BITS · HARD

Vasiliy's Multiset

HARD bits ▶ SOLVE ON CODEFORCESCodeforces 706D, rated 1800. Submit the Python tab as PyPy3.
SIGNAL — WHAT GIVES IT AWAY

A multiset starts as {0}. Handle + x, − x (remove one copy) and ? x, the largest x XOR y over the y in the multiset.

INTUITION

The binary trie answers a maximum XOR as in unit 10, but now numbers also leave. Deleting nodes is awkward, since other numbers share them. Each node keeps a count of the numbers passing through it instead: + adds 1 along the path and − takes 1 away. A query then treats a child with count 0 as missing. The 0 that is always present keeps the trie from ever being empty.

STEPS
  1. Each node keeps a count of the numbers through it
  2. + x adds 1 to every node on x's path, making nodes as needed; − x subtracts 1
  3. ? x walks down taking the opposite bit when that child's count is above 0
  4. Insert 0 first, so a query always has a path
BRUTEO(q²)
→
OPTIMALO(30 · q)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;

int main() {
    int q;
    scanf("%d", &q);
    vector<array<int, 2>> next(1, {{0, 0}});
    vector<int> cnt(1, 0);                     // numbers passing through each node
    auto add = [&](int x, int d) {
        int cur = 0;
        for (int b = 29; b >= 0; b--) {
            int bit = x >> b & 1;
            if (!next[cur][bit]) {
                next[cur][bit] = next.size();
                next.push_back({{0, 0}});
                cnt.push_back(0);
            }
            cur = next[cur][bit];
            cnt[cur] += d;
        }
    };
    add(0, 1);                                 // 0 is always there
    while (q--) {
        char op;
        int x;
        scanf(" %c %d", &op, &x);
        if (op == '+') add(x, 1);
        else if (op == '-') add(x, -1);
        else {
            int cur = 0, best = 0;
            for (int b = 29; b >= 0; b--) {
                int want = (x >> b & 1) ^ 1;
                int v = next[cur][want];
                if (v && cnt[v] > 0) { best |= 1 << b; cur = v; }   // a live number has it
                else cur = next[cur][want ^ 1];
            }
            printf("%d\n", best);
        }
    }
}
TIMEO(30 · q)30 bits per query
SPACEO(30 · q)one node per new bit-prefix
TRAP

A child that exists but is empty. After + 8 and − 8, the node for 8's top bit is still there with count 0. A query that only checks whether the child exists walks into it, and on ? 3 prints 11 when the only number left is 0, so the answer is 3.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
47 / SIGNALS WHEN YOU SEE X, REACH FOR Y

WHICH MOVE, AND WHAT GIVES IT AWAY

Eleven moves, and each has a phrase in the statement that gives it away.

MANY WORDS, AND QUESTIONS ABOUT THEIR PREFIXES

insert once; each question walks one path

A NODE PER PREFIXO(L)
REPLACE OR DROP BY THE SHORTEST PREFIX THAT IS A WORD

walk, and stop at the first ring

STOP AT THE FIRST WORDO(L)
A WORD BUILT ONE LETTER AT A TIME

every prefix is a word: step only into rings

ONLY THROUGH WORDSO(total)
SUGGEST THE SMALLEST FEW WITH A PREFIX

sort, insert, keep the first three at each node

THREE AT EVERY NODEO(total)
A PATTERN WITH WILDCARDS

a letter goes one way, a dot every way

A DOT TRIES EVERY CHILDO(26ᵈ · L)
MANY WORDS ON ONE BOARD

one search per cell, steered by the trie

THE BOARD AND THE TRIEO(mn · 3ᴸ)
BUILD A STRING FROM DICTIONARY WORDS

dp over i, walking the trie from i

EVERY WORD FROM HEREO(n · L)
A SUFFIX OF A STREAM, A WORD READ BACKWARDS

insert the words reversed

READ BACKWARDSO(L)
DICTIONARY ORDER OF 1 TO n

the numbers are a digit trie: count a subtree

COUNT, DO NOT BUILDO(log² n)
THE LARGEST XOR UNDER A LIMIT

a trie of bits, the queries sorted by the limit

BITS AS A PATHO(30)
XOR OVER A SET THAT LOSES NUMBERS

counts on the nodes instead of deletions

COUNTS LET IT FORGETO(30)
INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
48 / RECALL RETRIEVAL, NOT RECOGNITION · 1 OF 2

NAME THE MOVE FROM THE STATEMENT

DRILL 01 · TRANSFER

Count the distinct substrings of a string of 1,000 letters. Which move?

Insert every suffix. Each substring is a prefix of some suffix, so each node is one distinct substring. It is A2Z's Number of Distinct Substrings.

DRILL 02 · TRANSFER

Maximum XOR of Two Numbers in an Array. Which move?

Unit 10 without the limit: insert every number, then walk each one taking the opposite bit. It lives in bit-manipulation.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
49 / RECALL RETRIEVAL, NOT RECOGNITION · 2 OF 2

NAME THE MOVE FROM THE STATEMENT

DRILL 01 · TRANSFER

Longest Common Prefix of a list of strings. Which move?

Insert every string and walk from the root while there is one child and no ring. It is in the strings deck, where a scan does the same.

DRILL 02 · TRANSFER

Magic Dictionary: is a word one changed letter away from a stored one? Which move?

Search as unit 5 does, but a mismatch may try every other child once. After that, the rest of the word must match exactly.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
50 / TRAPS PLAUSIBLE, WRONG, AND SILENT

SIX WAYS TO BE PLAUSIBLY WRONG

None of these fail the samples. Each one fails a hidden test.

A SEARCH THAT ONLY WALKS

After insert("apple"), the walk for "app" reaches a node. search must also find a ring there.

THE LONGEST ROOT, NOT THE SHORTEST

Replace Words stops at the first ring. Walking on and keeping the last one turns aaaa into aaa.

A LETTER TRIE FOR PATHS

Letter by letter, "/a/b" is a prefix of "/a/bc", which is not its sub-folder. Split at "/".

INSERTING BEFORE SORTING

A node keeps the first three products to reach it. Only in sorted order are those the smallest.

A WORD FOUND TWICE

Word Search II reaches a word's node once per path. Clear the word the first time.

A CHILD THAT EXISTS BUT IS EMPTY

After − x its nodes stay, with count 0. A query must test the count, not the pointer.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
51 / CHEATSHEET REVISION SURFACE

ONE SCREEN, THE WHOLE DECK

Eleven moves on one page. The right column is the cue for each.

ALGORITHM
TIME
SPACE
REACH FOR IT WHEN
A node per prefix
O(L)
O(total)
walk; grow a missing child; ring at the end
Stop at the first word
O(L)
O(total)
the first ring on the path is the shortest root
Only through words
O(total)
O(total)
search a to z, entering nodes with a ring
Three at every node
O(total)
O(total)
sort; each node keeps the first three
A dot tries every child
O(26ᵈ · L)
O(total)
a letter: one child; a dot: every child
The board and the trie
O(mn · 3ᴸ)
O(total)
step only to a child; clear found words; cut
Every word from here
O(n · L)
O(n)
dp[i] += dp[j + 1] at each ring from i
Read backwards
O(L) per query
O(total)
insert reversed; walk back from the newest
Count, do not build
O(log² n)
O(1)
levels [10ᵏp, 10ᵏp + 10ᵏ − 1], cut at n
Bits as a path
O(30) per query
O(30n)
take the opposite bit; queries sorted by m
Counts let it forget
O(30) per op
O(30q)
+1 or −1 down the path; count 0 is missing
INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
52 / CLOSE MODULE 20 · TRIES

TAKE IT NOW

Words that start alike shared a path. One walk answered search and startsWith, stopped at the shortest root, and stepped only through words. Each node kept its first three products, and a dot tried every child. The trie steered a board, a dp over a string and a reversed stream. The numbers 1 to n were a trie never built, and bits made paths whose counts let numbers leave.

00%
OF THIS DECK SOLVED
← ALL TOPICS← HEAPSGREEDY →

Module 20. Fifteen problems: thirteen on LeetCode, one on CSES and one on Codeforces. Next in the sheet: greedy.

INVARIANT · TRIES · A NODE PER PREFIX, ONE WALK PER WORD · TRIES
■ TOO SMALL TO READ
1280×720
INVARIANT · MODULE 20 · TRIES

This one needs a laptop

Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.

Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.

YOUR SCREEN0 × 0
NEEDED1060 × 610
WHAT IS WAITING ON THE LAPTOP
WATCH IT RUN, THEN RUN IT FROM MEMORY
Your progress is saved per device, so anything you tick on the laptop will be waiting there.