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.
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.
A word walks down from the root and grows a node for each missing letter. Its last node gets a ring.
search and startsWith walk the string down the same way. search also needs a ring where the walk stops.
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.
In that trie: search("ap") and startsWith("ap")?
The walk reaches the first p in both. It has no ring, so search is false.
Build a structure with insert, search for a whole word, and startsWith for a prefix.
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.
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; } };
class Trie { private static class Node { Node[] next = new Node[26]; boolean end; // a word ends here } private final Node root = new Node(); private Node walk(String s) { // the node for s, or null Node cur = root; for (char ch : s.toCharArray()) { cur = cur.next[ch - 'a']; if (cur == null) return null; } return cur; } public void insert(String word) { Node cur = root; for (char ch : word.toCharArray()) { int c = ch - 'a'; if (cur.next[c] == null) cur.next[c] = new Node(); // a new prefix cur = cur.next[c]; } cur.end = true; } public boolean search(String word) { Node n = walk(word); return n != null && n.end; } public boolean startsWith(String prefix) { return walk(prefix) != null; } }
class Trie: def __init__(self): self.root = {} # letter -> child; "$" marks a word's end def _walk(self, s): # the node for s, or None cur = self.root for ch in s: if ch not in cur: return None cur = cur[ch] return cur def insert(self, word): cur = self.root for ch in word: cur = cur.setdefault(ch, {}) # a new prefix if missing cur["$"] = True def search(self, word): node = self._walk(word) return node is not None and "$" in node def startsWith(self, prefix): return self._walk(prefix) is not None
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.
Two arrays of positive integers. Find the longest common prefix of digits over every pair (x from arr1, y from arr2).
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.
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; }
public int longestCommonPrefix(int[] arr1, int[] arr2) { int[][] next = new int[arr1.length * 9 + 1][10]; // 0 = no child int size = 1; for (int x : arr1) { int cur = 0; for (char ch : Integer.toString(x).toCharArray()) { int d = ch - '0'; if (next[cur][d] == 0) next[cur][d] = size++; cur = next[cur][d]; } } int best = 0; for (int y : arr2) { int cur = 0, len = 0; for (char ch : Integer.toString(y).toCharArray()) { int d = ch - '0'; if (next[cur][d] == 0) break; // the paths part here cur = next[cur][d]; len++; } best = Math.max(best, len); } return best; }
def longestCommonPrefix(arr1, arr2): root = {} for x in arr1: cur = root for ch in str(x): cur = cur.setdefault(ch, {}) best = 0 for y in arr2: cur, n = root, 0 for ch in str(y): if ch not in cur: # the paths part here break cur = cur[ch] n += 1 best = max(best, n) return best
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.
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.
Each word walks down the trie of roots. The first ring it meets is the shortest root that starts it.
replaceWords(["a", "aa", "aaa"], "aaaa bbb")?
aaaa meets the ring on a first. bbb falls off at once and stays.
Replace each word of a sentence by the shortest root from a dictionary that starts it, if any does.
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.
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; }
public String replaceWords(List<String> dictionary, String sentence) { int total = 1; for (String w : dictionary) total += w.length(); int[][] next = new int[total][26]; boolean[] end = new boolean[total]; int size = 1; for (String w : dictionary) { int cur = 0; for (char ch : w.toCharArray()) { int c = ch - 'a'; if (next[cur][c] == 0) next[cur][c] = size++; cur = next[cur][c]; } end[cur] = true; } StringBuilder out = new StringBuilder(); for (String word : sentence.split(" ")) { int cur = 0, len = 0; for (char ch : word.toCharArray()) { cur = next[cur][ch - 'a']; if (cur == 0) break; // no root fits len++; if (end[cur]) break; // the shortest root } if (out.length() > 0) out.append(' '); out.append(cur != 0 && end[cur] ? word.substring(0, len) : word); } return out.toString(); }
def replaceWords(dictionary, sentence): root = {} for w in dictionary: cur = root for ch in w: cur = cur.setdefault(ch, {}) cur["$"] = True out = [] for word in sentence.split(): cur, pre = root, word # no root yet: keep the word for i, ch in enumerate(word): if ch not in cur: break cur = cur[ch] if "$" in cur: # the shortest root pre = word[:i + 1] break out.append(pre) return " ".join(out)
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.
A list of folder paths. Remove every sub-folder, a path that starts with another path followed by "/".
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.
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; }
public List<String> removeSubfolders(String[] folder) { List<Map<String, Integer>> next = new ArrayList<>(); List<Integer> end = new ArrayList<>(); // the folder that ends here, or -1 next.add(new HashMap<>()); end.add(-1); for (int i = 0; i < folder.length; i++) { int cur = 0; for (String part : folder[i].substring(1).split("/")) { Integer nx = next.get(cur).get(part); if (nx == null) { nx = next.size(); next.get(cur).put(part, nx); next.add(new HashMap<>()); end.add(-1); } cur = nx; } end.set(cur, i); } List<String> out = new ArrayList<>(); Deque<Integer> st = new ArrayDeque<>(); st.push(0); while (!st.isEmpty()) { int u = st.pop(); if (end.get(u) >= 0) { // everything below is a sub-folder out.add(folder[end.get(u)]); continue; } for (int v : next.get(u).values()) st.push(v); } return out; }
def removeSubfolders(folder): root = {} for f in folder: cur = root for part in f.split("/")[1:]: cur = cur.setdefault(part, {}) cur["$"] = f # a folder ends here out, st = [], [root] while st: node = st.pop() if "$" in node: # everything below is a sub-folder out.append(node["$"]) continue st.extend(node.values()) return out
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.
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.
Why split the paths at "/" instead of inserting letters?
A sub-folder continues with "/". As parts, b and bc are different edges.
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.
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.
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.
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.
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.
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; }
public String longestWord(String[] words) { int total = 1; for (String w : words) total += w.length(); int[][] next = new int[total][26]; boolean[] end = new boolean[total]; end[0] = true; // the root: the empty word int size = 1; for (String w : words) { int cur = 0; for (char ch : w.toCharArray()) { int c = ch - 'a'; if (next[cur][c] == 0) next[cur][c] = size++; cur = next[cur][c]; } end[cur] = true; } StringBuilder path = new StringBuilder(); String[] best = {""}; dfs(0, next, end, path, best); return best[0]; } void dfs(int u, int[][] next, boolean[] end, StringBuilder path, String[] best) { if (path.length() > best[0].length()) best[0] = path.toString(); for (int c = 0; c < 26; c++) { int v = next[u][c]; if (v == 0 || !end[v]) continue; // only words lead further down path.append((char) ('a' + c)); dfs(v, next, end, path, best); path.setLength(path.length() - 1); } }
def longestWord(words): root = {} for w in words: cur = root for ch in w: cur = cur.setdefault(ch, {}) cur["$"] = True best, st = "", [(root, "")] while st: node, path = st.pop() if len(path) > len(best) or (len(path) == len(best) and path < best): best = path for ch, child in node.items(): if ch != "$" and "$" in child: # only words lead further down st.append((child, path + ch)) return best
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.
Products go in sorted, and each node keeps the first three that pass it. Typing walks one node per letter and reads its list.
Products mobile, mouse, moneypot, monitor, mousepad. The list after typing "mou"?
Only two products start with "mou". Sorted, mouse comes before mousepad.
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.
After each letter of searchWord is typed, suggest the three smallest products that start with what has been typed.
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.
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; }
public List<List<String>> suggestedProducts(String[] products, String searchWord) { Arrays.sort(products); // smallest first int total = 1; for (String p : products) total += p.length(); int[][] next = new int[total][26]; List<List<String>> top = new ArrayList<>(); top.add(new ArrayList<>()); int size = 1; for (String p : products) { int cur = 0; for (char ch : p.toCharArray()) { int c = ch - 'a'; if (next[cur][c] == 0) { next[cur][c] = size++; top.add(new ArrayList<>()); } cur = next[cur][c]; if (top.get(cur).size() < 3) top.get(cur).add(p); } } List<List<String>> out = new ArrayList<>(); int cur = 0; // -1 once off the trie for (char ch : searchWord.toCharArray()) { if (cur != -1) cur = next[cur][ch - 'a'] != 0 ? next[cur][ch - 'a'] : -1; out.add(cur == -1 ? new ArrayList<>() : new ArrayList<>(top.get(cur))); } return out; }
def suggestedProducts(products, searchWord): root = {"top": []} for p in sorted(products): # smallest first cur = root for ch in p: cur = cur.setdefault(ch, {"top": []}) if len(cur["top"]) < 3: cur["top"].append(p) out, cur = [], root for ch in searchWord: cur = cur.get(ch) if cur else None # None once off the trie out.append(list(cur["top"]) if cur else []) return out
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.
A letter follows one edge. A dot tries each child in turn until one of them reaches a word.
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.
Only "bad" is stored. search("b.")?
The walk reaches ba, but no word ends there.
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.
addWord stores a word, and search asks whether any stored word matches a pattern in which "." stands for any letter.
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.
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); } };
class WordDictionary { private static class Node { Node[] next = new Node[26]; boolean end; } private final Node root = new Node(); private boolean match(Node u, String w, int i) { if (i == w.length()) return u.end; char ch = w.charAt(i); if (ch != '.') { Node v = u.next[ch - 'a']; return v != null && match(v, w, i + 1); } for (Node v : u.next) // a dot: try every child if (v != null && match(v, w, i + 1)) return true; return false; } public void addWord(String word) { Node cur = root; for (char ch : word.toCharArray()) { int c = ch - 'a'; if (cur.next[c] == null) cur.next[c] = new Node(); cur = cur.next[c]; } cur.end = true; } public boolean search(String word) { return match(root, word, 0); } }
class WordDictionary: def __init__(self): self.root = {} def addWord(self, word): cur = self.root for ch in word: cur = cur.setdefault(ch, {}) cur["$"] = True def _match(self, node, w, i): if i == len(w): return "$" in node if w[i] != ".": return w[i] in node and self._match(node[w[i]], w, i + 1) return any(self._match(child, w, i + 1) # a dot: try every child for ch, child in node.items() if ch != "$") def search(self, word): return self._match(self.root, word, 0)
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.
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.
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.
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.
Why put the letter back after the neighbours are searched?
# only means "on this path". Once the search leaves, the cell is free.
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.
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.
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; }
private static class Node { Node[] next = new Node[26]; int word = -1, kids = 0; } private char[][] board; private String[] words; private List<String> out; public List<String> findWords(char[][] board, String[] words) { this.board = board; this.words = words; out = new ArrayList<>(); Node root = new Node(); for (int i = 0; i < words.length; i++) { Node cur = root; for (char ch : words[i].toCharArray()) { int c = ch - 'a'; if (cur.next[c] == null) { cur.next[c] = new Node(); cur.kids++; } cur = cur.next[c]; } cur.word = i; } for (int r = 0; r < board.length; r++) for (int c = 0; c < board[0].length; c++) if (root.next[board[r][c] - 'a'] != null) dfs(r, c, root); return out; } private void dfs(int r, int c, Node parent) { char ch = board[r][c]; Node u = parent.next[ch - 'a']; if (u.word >= 0) { out.add(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 >= board.length || nc < 0 || nc >= board[0].length || board[nr][nc] == '#') continue; if (u.next[board[nr][nc] - 'a'] != null) 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'] = null; parent.kids--; } }
def findWords(board, words): root = {} for w in words: cur = root for ch in w: cur = cur.setdefault(ch, {}) cur["$"] = w m, n, out = len(board), len(board[0]), [] def dfs(r, c, parent): ch = board[r][c] node = parent[ch] if "$" in node: # found: once each out.append(node.pop("$")) board[r][c] = "#" # used on this path for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)): if 0 <= nr < m and 0 <= nc < n and board[nr][nc] in node: dfs(nr, nc, node) board[r][c] = ch if not node: # nothing left below: cut it off parent.pop(ch) for r in range(m): for c in range(n): if board[r][c] in root: dfs(r, c, root) return out
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.
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].
s = "aaa", words a and aa. In how many ways can s be built?
a + a + a, a + aa and aa + a.
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.
A string and a dictionary. Count the ways to build the string by joining dictionary words, modulo 10⁹ + 7.
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.
#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"; }
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String s = in.readLine().trim(); int k = Integer.parseInt(in.readLine().trim()); String[] words = new String[k]; int total = 1; for (int i = 0; i < k; i++) { words[i] = in.readLine().trim(); total += words[i].length(); } int[] next = new int[total * 26]; // next[node * 26 + letter], 0 = none boolean[] end = new boolean[total]; int size = 1; for (String w : words) { int cur = 0; for (int i = 0; i < w.length(); i++) { int c = w.charAt(i) - 'a'; if (next[cur * 26 + c] == 0) next[cur * 26 + c] = size++; cur = next[cur * 26 + c]; } end[cur] = true; } final long MOD = 1_000_000_007L; int n = s.length(); long[] dp = new long[n + 1]; // 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 * 26 + s.charAt(j) - 'a']; if (cur == 0) break; if (end[cur]) dp[i] = (dp[i] + dp[j + 1]) % MOD; } } System.out.println(dp[0]); } }
import sys def main(): data = sys.stdin.buffer.read().split() s, k = data[0], int(data[1]) child, end, size = {}, set(), 1 # child[node * 32 + letter] -> node for w in data[2:2 + k]: cur = 0 for ch in w: key = cur * 32 + ch - 97 nxt = child.get(key) if nxt is None: nxt = child[key] = size size += 1 cur = nxt end.add(cur) MOD = 10 ** 9 + 7 n = len(s) dp = [0] * (n + 1) # dp[i]: ways to build s[i:] dp[n] = 1 for i in range(n - 1, -1, -1): cur, tot = 0, 0 for j in range(i, n): # every word that starts at i cur = child.get(cur * 32 + s[j] - 97) if cur is None: break if cur in end: tot += dp[j + 1] dp[i] = tot % MOD print(dp[0]) main()
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.
The words go in reversed. A query walks back from the newest letter, so every suffix shares one walk.
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.
Why insert the words reversed?
One walk back from the newest letter passes every suffix's start at once.
Letters arrive one at a time. After each, say whether some suffix of the stream is a word from the list.
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.
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; } };
class StreamChecker { private int[][] next; private boolean[] end; private final StringBuilder seen = new StringBuilder(); // the letters so far private int longest = 0; public StreamChecker(String[] words) { int total = 1; for (String w : words) total += w.length(); next = new int[total][26]; end = new boolean[total]; int size = 1; for (String w : words) { int cur = 0; for (int i = w.length() - 1; i >= 0; i--) { // each word reversed int c = w.charAt(i) - 'a'; if (next[cur][c] == 0) next[cur][c] = size++; cur = next[cur][c]; } end[cur] = true; longest = Math.max(longest, w.length()); } } public boolean query(char letter) { seen.append(letter); int cur = 0, n = seen.length(); for (int i = n - 1; i >= 0 && i >= n - longest; i--) { cur = next[cur][seen.charAt(i) - 'a']; if (cur == 0) return false; // no word ends this way if (end[cur]) return true; } return false; } }
class StreamChecker: def __init__(self, words): self.root = {} for w in words: cur = self.root for ch in reversed(w): # each word reversed cur = cur.setdefault(ch, {}) cur["$"] = True self.longest = max(map(len, words)) self.seen = [] def query(self, letter): self.seen.append(letter) cur, n = self.root, len(self.seen) for i in range(n - 1, max(-1, n - 1 - self.longest), -1): cur = cur.get(self.seen[i]) if cur is None: # no word ends this way return False if "$" in cur: return True return False
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.
Unique words. Find every pair (i, j), i ≠ j, whose concatenation words[i] + words[j] is a palindrome.
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.
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; }
public List<List<Integer>> palindromePairs(String[] words) { int total = 1; for (String w : words) total += w.length(); int[][] next = new int[total][26]; int[] word = new int[total]; // the word whose reverse ends here Arrays.fill(word, -1); List<List<Integer>> rest = new ArrayList<>(); // words whose reverse goes on as a palindrome rest.add(new ArrayList<>()); int size = 1; for (int j = 0; j < words.length; j++) { String w = words[j]; int cur = 0; for (int i = w.length() - 1; i >= 0; i--) { // w reversed if (pal(w, 0, i)) rest.get(cur).add(j); // what is left reads the same int c = w.charAt(i) - 'a'; if (next[cur][c] == 0) { next[cur][c] = size++; rest.add(new ArrayList<>()); } cur = next[cur][c]; } word[cur] = j; rest.get(cur).add(j); // nothing left: that reads the same too } List<List<Integer>> out = new ArrayList<>(); for (int i = 0; i < words.length; i++) { String w = words[i]; int cur = 0, n = w.length(); for (int k = 0; k < n && cur != -1; k++) { if (word[cur] >= 0 && word[cur] != i && pal(w, k, n - 1)) out.add(Arrays.asList(i, word[cur])); // w = reverse(other) + palindrome int c = w.charAt(k) - 'a'; cur = next[cur][c] != 0 ? next[cur][c] : -1; } if (cur != -1) for (int j : rest.get(cur)) if (j != i) out.add(Arrays.asList(i, j)); // reverse(other) = w + palindrome } return out; } boolean pal(String s, int i, int j) { // s[i..j] reads the same both ways while (i < j) if (s.charAt(i++) != s.charAt(j--)) return false; return true; }
def palindromePairs(words): root = {"rest": []} # "#": the word whose reverse ends here for j, w in enumerate(words): cur = root for i in range(len(w) - 1, -1, -1): # w reversed if w[:i + 1] == w[i::-1]: # what is left reads the same cur["rest"].append(j) cur = cur.setdefault(w[i], {"rest": []}) cur["#"] = j cur["rest"].append(j) # nothing left: that reads the same too out = [] for i, w in enumerate(words): cur = root for k, ch in enumerate(w): j = cur.get("#") if j is not None and j != i and w[k:] == w[k:][::-1]: out.append([i, j]) # w = reverse(other) + palindrome cur = cur.get(ch) if cur is None: break if cur is not None: out.extend([i, j] for j in cur["rest"] if j != i) # reverse(other) = w + palindrome return out
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.
palindromePairs(["abcd", "dcba", "lls", "s", "sssll"]): how many pairs?
(0, 1) and (1, 0), then s + lls = slls and lls + sssll = llssssll.
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 first six numbers of lexicalOrder(13)?
Dictionary order is the digit trie in preorder: 1, then its children 10 to 13, then 2.
findKthNumber(13, 2)?
count(1) = 5 is more than k = 1, so the walk goes down from 1 to 10.
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.
List the numbers 1 to n in dictionary order, in O(n) time and O(1) extra space.
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.
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; }
public List<Integer> lexicalOrder(int n) { List<Integer> out = new ArrayList<>(); int cur = 1; for (int i = 0; i < n; i++) { out.add(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; }
def lexicalOrder(n): out, cur = [], 1 for _ in range(n): out.append(cur) if cur * 10 <= n: # down to the first child cur *= 10 else: while cur % 10 == 9 or cur + 1 > n: # no next sibling: climb cur //= 10 cur += 1 return out
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.
Return the k-th number in dictionary order among 1 to n, for n up to 10⁹.
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.
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; }
public int findKthNumber(int n, int k) { long cur = 1; k -= 1; // cur = 1 is the first number while (k > 0) { long c = count(cur, n); if (c <= k) { k -= c; cur++; } // skip the whole subtree else { k -= 1; cur *= 10; } // the answer is inside: go down } return (int) cur; } long count(long p, int n) { // how many of 1..n start with p long cnt = 0, lo = p, hi = p; while (lo <= n) { cnt += Math.min(n, hi) - lo + 1; lo *= 10; hi = hi * 10 + 9; } return cnt; }
def findKthNumber(n, k): def count(p): # how many of 1..n start with p cnt, lo, hi = 0, p, p while lo <= n: cnt += min(n, hi) - lo + 1 lo *= 10 hi = hi * 10 + 9 return cnt cur, k = 1, k - 1 # cur = 1 is the first number while k > 0: c = count(cur) if c <= k: # skip the whole subtree k -= c cur += 1 else: # the answer is inside: go down k -= 1 cur *= 10 return cur
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.
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.
maximizeXor([0, 1, 2, 3, 4], [[3, 1], [1, 3], [5, 6]])?
3 XOR 0, 1 XOR 2 and 5 XOR 2.
Why take the opposite bit at the highest bit first?
2ᵇ is more than 2ᵇ − 1, the most that every lower bit can add.
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.
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.
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; }
public int[] maximizeXor(int[] nums, int[][] queries) { Arrays.sort(nums); Integer[] order = new Integer[queries.length]; for (int i = 0; i < order.length; i++) order[i] = i; Arrays.sort(order, (a, b) -> Integer.compare(queries[a][1], queries[b][1])); int[][] next = new int[nums.length * 30 + 1][2]; int size = 1, j = 0; int[] ans = new int[queries.length]; for (int q : order) { int x = queries[q][0], m = queries[q][1]; for (; j < nums.length && 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] == 0) next[cur][bit] = size++; 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] != 0) { best |= 1 << b; cur = next[cur][want]; } else cur = next[cur][want ^ 1]; } ans[q] = best; } return ans; }
def maximizeXor(nums, queries): nums = sorted(nums) order = sorted(range(len(queries)), key=lambda q: queries[q][1]) nxt, ans, j = [[0, 0]], [0] * len(queries), 0 for q in order: x, m = queries[q] while j < len(nums) and nums[j] <= m: # every num <= m goes in cur = 0 for b in range(29, -1, -1): bit = nums[j] >> b & 1 if not nxt[cur][bit]: nxt[cur][bit] = len(nxt) nxt.append([0, 0]) cur = nxt[cur][bit] j += 1 if j == 0: # nothing is small enough ans[q] = -1 continue cur = best = 0 for b in range(29, -1, -1): want = (x >> b & 1) ^ 1 # the opposite bit sets this one if nxt[cur][want]: best |= 1 << b cur = nxt[cur][want] else: cur = nxt[cur][want ^ 1] ans[q] = best return ans
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.
Each node counts the numbers that pass through it. − x lowers the counts, and a query treats a count of 0 as no child.
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.
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.
A multiset starts as {0}. Handle + x, − x (remove one copy) and ? x, the largest x XOR y over the y in the multiset.
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.
#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); } } }
import java.io.*; import java.util.*; public class Main { static int[][] next; static int[] cnt; // numbers passing through each node static int size = 1; static void add(int x, int d) { int cur = 0; for (int b = 29; b >= 0; b--) { int bit = x >> b & 1; if (next[cur][bit] == 0) next[cur][bit] = size++; cur = next[cur][bit]; cnt[cur] += d; } } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int q = Integer.parseInt(in.readLine().trim()); next = new int[30 * (q + 1) + 1][2]; cnt = new int[30 * (q + 1) + 1]; size = 1; add(0, 1); // 0 is always there StringBuilder out = new StringBuilder(); for (int i = 0; i < q; i++) { StringTokenizer st = new StringTokenizer(in.readLine()); char op = st.nextToken().charAt(0); int x = Integer.parseInt(st.nextToken()); 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 != 0 && cnt[v] > 0) { best |= 1 << b; cur = v; } // a live number has it else cur = next[cur][want ^ 1]; } out.append(best).append('\n'); } } System.out.print(out); } }
import sys def main(): data = sys.stdin.buffer.read().split() q = int(data[0]) nxt, cnt = [[0, 0]], [0] # numbers passing through each node def add(x, d): cur = 0 for b in range(29, -1, -1): bit = x >> b & 1 if not nxt[cur][bit]: nxt[cur][bit] = len(nxt) nxt.append([0, 0]) cnt.append(0) cur = nxt[cur][bit] cnt[cur] += d add(0, 1) # 0 is always there out = [] for i in range(q): op, x = data[1 + 2 * i], int(data[2 + 2 * i]) if op == b"+": add(x, 1) elif op == b"-": add(x, -1) else: cur = best = 0 for b in range(29, -1, -1): want = (x >> b & 1) ^ 1 v = nxt[cur][want] if v and cnt[v] > 0: # a live number has that bit best |= 1 << b cur = v else: cur = nxt[cur][want ^ 1] out.append(best) print("\n".join(map(str, out))) main()
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.
Eleven moves, and each has a phrase in the statement that gives it away.
insert once; each question walks one path
A NODE PER PREFIXO(L)walk, and stop at the first ring
STOP AT THE FIRST WORDO(L)every prefix is a word: step only into rings
ONLY THROUGH WORDSO(total)sort, insert, keep the first three at each node
THREE AT EVERY NODEO(total)a letter goes one way, a dot every way
A DOT TRIES EVERY CHILDO(26ᵈ · L)one search per cell, steered by the trie
THE BOARD AND THE TRIEO(mn · 3ᴸ)dp over i, walking the trie from i
EVERY WORD FROM HEREO(n · L)insert the words reversed
READ BACKWARDSO(L)the numbers are a digit trie: count a subtree
COUNT, DO NOT BUILDO(log² n)a trie of bits, the queries sorted by the limit
BITS AS A PATHO(30)counts on the nodes instead of deletions
COUNTS LET IT FORGETO(30)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.
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.
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.
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.
None of these fail the samples. Each one fails a hidden test.
After insert("apple"), the walk for "app" reaches a node. search must also find a ring there.
Replace Words stops at the first ring. Walking on and keeping the last one turns aaaa into aaa.
Letter by letter, "/a/b" is a prefix of "/a/bc", which is not its sub-folder. Split at "/".
A node keeps the first three products to reach it. Only in sorted order are those the smallest.
Word Search II reaches a word's node once per path. Clear the word the first time.
After − x its nodes stay, with count 0. A query must test the count, not the pointer.
Eleven moves on one page. The right column is the cue for each.
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.
Module 20. Fifteen problems: thirteen on LeetCode, one on CSES and one on Codeforces. Next in the sheet: greedy.
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.