Construct a trie (insert / search / startsWith)Medium1 approach
Problem
Implement a prefix tree with insert(word), search(word) (is this exact word stored?) and startsWith(prefix) (does any stored word begin with this prefix?).
Example 1
Input: insert("apple"), search("apple"), search("app"), startsWith("app"), insert("app"), search("app")
Output: true, false, true, trueAlso asked as: Construct a trie from scratch
1. Nodes with a children map and an end flag
Time O(L) per opSpace O(total chars)
Each node holds a map char→child and a boolean "is a word end". Insert/search/prefix all walk character by character.
class Trie { constructor() { this.root = { children: new Map(), end: false }; } insert(word) { let node = this.root; for (const c of word) { if (!node.children.has(c)) node.children.set(c, { children: new Map(), end: false }); node = node.children.get(c); } node.end = true; } #find(prefix) { let node = this.root; for (const c of prefix) { if (!node.children.has(c)) return null; node = node.children.get(c); } return node; } search(word) { const n = this.#find(word); return !!n && n.end; } startsWith(prefix) { return this.#find(prefix) !== null; }}Shortest unique prefix for every wordMedium1 approach
Problem
Given a list of words where no word is a prefix of another, return for each word the shortest prefix that identifies it uniquely.
Example 1
Input: ["zebra", "dog", "duck", "dove"] Output: ["z", "dog", "du", "dov"]
Also asked as: Find shortest unique prefix for every word in a given list
1. Trie with per-node pass-through counts
Time O(total chars)Space O(total chars)
Insert all words, storing at each node how many words pass through it. For each word, the shortest unique prefix ends at the first node whose count is 1.
function shortestUniquePrefixes(words) { const root = { children: new Map(), count: 0 }; for (const w of words) { let node = root; for (const c of w) { if (!node.children.has(c)) node.children.set(c, { children: new Map(), count: 0 }); node = node.children.get(c); node.count++; } } return words.map((w) => { let node = root, prefix = ''; for (const c of w) { node = node.children.get(c); prefix += c; if (node.count === 1) break; } return prefix; });}Word Break (trie solution)Medium1 approach
Problem
Same as Word Break — can s be split into dictionary words? — but store the dictionary in a trie, so that from each start index you walk forward only along real word prefixes.
Example 1
Input: s = "ilikesamsung", dict = ["i", "like", "sam", "sung", "samsung"] Output: true
Also asked as: Word Break Problem | (Trie solution)
1. DP over prefixes, dictionary stored in a trie
Time O(n² ) worst, faster in practiceSpace O(dict)
dp[i] = s[0..i) is breakable. From each true dp[j], walk the trie along s[j..] and set dp[k] wherever you hit a word end.
function wordBreakTrie(s, dict) { const root = { children: new Map(), end: false }; for (const w of dict) { let node = root; for (const c of w) { if (!node.children.has(c)) node.children.set(c, { children: new Map(), end: false }); node = node.children.get(c); } node.end = true; } const dp = Array(s.length + 1).fill(false); dp[0] = true; for (let i = 0; i < s.length; i++) { if (!dp[i]) continue; let node = root; for (let j = i; j < s.length; j++) { const c = s[j]; if (!node.children.has(c)) break; node = node.children.get(c); if (node.end) dp[j + 1] = true; } } return dp[s.length];}Implement a phone directory (prefix search)Medium1 approach
Problem
Given a list of contacts and a query string, return for each prefix of the query (its first 1, 2, … characters) the sorted list of matching contacts, or "0" if none match.
Example 1
Input: contacts = ["geeikistest", "geeksforgeeks", "geeksfortest"], query = "geeips" Output: g, ge, gee → all three; geei → [geeikistest]; geeip, geeips → 0
Also asked as: Implement a Phone Directory
1. Trie; DFS from the prefix node to list matches
Time O(L + matches)Space O(total chars)
Insert all contacts. For each successive prefix of a query, find its trie node and DFS to collect all words below it.
function phoneDirectory(contacts, query) { const root = { children: new Map(), end: false }; for (const name of contacts) { let node = root; for (const c of name) { if (!node.children.has(c)) node.children.set(c, { children: new Map(), end: false }); node = node.children.get(c); } node.end = true; } const collect = (node, prefix, out) => { if (node.end) out.push(prefix); for (const [c, child] of node.children) collect(child, prefix + c, out); }; const results = []; let node = root, prefix = ''; for (const c of query) { if (!node || !node.children.has(c)) { node = null; results.push([]); continue; } node = node.children.get(c); prefix += c; const out = []; collect(node, prefix, out); results.push(out.sort()); } return results; // one suggestion list per typed character}Print unique rows in a boolean matrixEasy1 approach
Problem
Print each distinct row of a binary matrix once, in order of first appearance.
Example 1
Input: [[1,1,0,1], [1,0,0,1], [1,1,0,1]] Output: 1 1 0 1, 1 0 0 1
Also asked as: Print unique rows in a given boolean matrix
1. Trie of rows (or a set of joined strings)
Time O(rows · cols)Space O(rows · cols)
Treat each row as a binary string; insert into a trie (or a Set). Print a row only the first time it is inserted.
function uniqueRows(matrix) { const seen = new Set(); const out = []; for (const row of matrix) { const key = row.join(''); if (!seen.has(key)) { seen.add(key); out.push(row); } } return out;}Design Add and Search Words Data StructureMedium1 approach
Problem
Design addWord(word) and search(word), where search's pattern may contain "." to match any single letter.
Example 1
Input: addWord("bad"), addWord("dad"), addWord("mad"), search("pad"), search("bad"), search(".ad"), search("b..")
Output: false, true, true, true1. Trie + DFS on "."
Time add O(L); search O(L) without dots, up to O(26^L) worst caseSpace O(total characters)
Insert normally. When searching, a "." branches into every child; a letter follows one edge.
class WordDictionary { constructor() { this.root = {}; } addWord(word) { let node = this.root; for (const ch of word) node = node[ch] ??= {}; node.end = true; } search(word) { const dfs = (node, i) => { if (i === word.length) return !!node.end; const ch = word[i]; if (ch !== '.') return !!node[ch] && dfs(node[ch], i + 1); for (const k in node) if (k !== 'end' && dfs(node[k], i + 1)) return true; return false; }; return dfs(this.root, 0); }}Word Search IIHard1 approach
Problem
Given a letter grid and a list of words, return every word that can be spelled by a path of adjacent cells (up, down, left or right) without reusing a cell within one word.
Example 1
Input: board = [["o","a","a","n"], ["e","t","a","e"], ["i","h","k","r"], ["i","f","l","v"]], words = ["oath","pea","eat","rain"] Output: ["eat", "oath"]
1. Trie of words + one grid DFS
Time O(R·C·4·3^(L−1)) worst caseSpace O(total characters)
Running Word Search once per word repeats work. Build a trie, then DFS from each cell following only trie edges. Store the word at its end node, and clear it once found to avoid duplicates.
function findWords(board, words) { const root = {}; for (const w of words) { let node = root; for (const ch of w) node = node[ch] ??= {}; node.word = w; } const R = board.length, C = board[0].length, res = []; const dfs = (r, c, parent) => { const ch = board[r][c], node = parent[ch]; if (!node) return; if (node.word) { res.push(node.word); node.word = null; } board[r][c] = '#'; for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) { const nr = r + dr, nc = c + dc; if (nr >= 0 && nc >= 0 && nr < R && nc < C && board[nr][nc] !== '#') dfs(nr, nc, node); } board[r][c] = ch; }; for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) dfs(r, c, root); return res;}Optimisation: delete a trie leaf once its word is found, so dead branches stop being explored.
Longest Word in DictionaryMedium1 approach
Problem
Return the longest word in the list that can be built one letter at a time, where every prefix (its first 1, 2, … letters) is also in the list. Break ties by the lexicographically smallest word.
Example 1
Input: ["a", "banana", "app", "appl", "ap", "apply", "apple"] Output: "apple"
"apply" is also buildable, but "apple" comes first alphabetically.
1. Sort + set of buildable words
Time O(n log n · L)Space O(n · L)
Sort words (shorter first, then lexicographically). A word is buildable if its prefix without the last char is buildable.
function longestWord(words) { words.sort(); const ok = new Set(['']); let best = ''; for (const w of words) { if (ok.has(w.slice(0, -1))) { ok.add(w); if (w.length > best.length) best = w; } } return best;}Trie version: insert all, then DFS only through nodes that end a word; track the deepest, earliest-lexicographic one.