4 drills · 4 pattern exercises · 10 micro drills
Patterns used in this topic, with difficulty breakdown.
Build a tree-like structure where each path from root to a node represents a prefix of inserted words. Support inserting words and checking if a word or prefix exists.
All 4 drills grouped by pattern. Each includes prompt, solution, and complexity.
In plain English: Build a tree-like structure where each path from root to a node represents a prefix of inserted words. Support inserting words and checking if a word or prefix exists.
Each node is a dictionary of children keyed by character. Insert walks the tree creating nodes; search walks and checks the end marker. Prefix search is just search without the end check.
Prompt
Implement a trie with insert, search, and startsWith methods.
Solution
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
# create missing child nodes along the path for each character
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def search(self, word):
node = self._find(word)
# must land on a node AND it must be a complete word, not just a prefix
return node is not None and node.is_end
def starts_with(self, prefix):
return self._find(prefix) is not None
def _find(self, prefix):
# traverse character-by-character; return None early if path doesn't exist
node = self.root
for ch in prefix:
if ch not in node.children:
return None
node = node.children[ch]
return node
# Test: t = Trie(); t.insert("apple")
# t.search("apple") == True; t.search("app") == False
# t.starts_with("app") == TrueIn plain English: Build a word dictionary that supports wildcard searches — a dot can match any letter.
Insert works like a normal trie. Search uses DFS: for regular chars, follow the child; for '.', branch into all children. The backtracking handles wildcards naturally.
Prompt
Design a data structure that supports adding words and searching for words where '.' can match any single character.
Solution
class WordDictionary:
def __init__(self):
self.children = {}
self.is_end = False
def add_word(self, word):
node = self
for ch in word:
if ch not in node.children:
node.children[ch] = WordDictionary()
node = node.children[ch]
node.is_end = True
def search(self, word):
return self._dfs(word, 0)
def _dfs(self, word, i):
if i == len(word):
return self.is_end
ch = word[i]
if ch == '.':
# wildcard: try every child
for child in self.children.values():
if child._dfs(word, i + 1):
return True
return False
if ch not in self.children:
return False
return self.children[ch]._dfs(word, i + 1)
# Test: d = WordDictionary()
# d.add_word("bad"); d.add_word("dad")
# d.search(".ad") == True; d.search("b..") == True
# d.search("b.") == FalseIn plain English: Given a grid of letters and a list of words, find which words can be spelled by tracing a path through adjacent cells.
Build a trie from the word list, then DFS from every cell. The trie prunes dead-end paths early — if the current prefix isn't in the trie, stop. Remove found words from the trie to avoid duplicates.
Prompt
Given an m x n board of characters and a list of words, return all words that can be formed by sequentially adjacent cells (horizontal or vertical). Each cell may only be used once per word.
Solution
def find_words(board, words):
root = {}
for w in words:
node = root
for ch in w:
node = node.setdefault(ch, {})
node['#'] = w # mark end with the word itself
m, n = len(board), len(board[0])
result = []
def dfs(i, j, node):
ch = board[i][j]
if ch not in node:
return
nxt = node[ch]
if '#' in nxt:
result.append(nxt.pop('#')) # found word, remove to dedup
board[i][j] = '.' # mark visited
for di, dj in ((1,0),(-1,0),(0,1),(0,-1)):
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and board[ni][nj] != '.':
dfs(ni, nj, nxt)
board[i][j] = ch # restore
if not nxt: # prune empty trie branches
del node[ch]
for i in range(m):
for j in range(n):
dfs(i, j, root)
return result
# Test: board = [["o","a","a","n"],["e","t","a","e"],
# ["i","h","k","r"],["i","f","l","v"]]
# find_words(board, ["oath","pea","eat","rain"]) == ["oath","eat"]In plain English: Find the longest word where every prefix of that word is also in the list.
Insert all words into a trie, marking end-of-word nodes. BFS level by level — only explore children that are complete words themselves. The last complete word found at the deepest level (lexicographically smallest) is the answer.
Prompt
Given a list of words, return the longest word that can be built one character at a time by other words in the list. If tied, return the lexicographically smallest.
Solution
from collections import deque
def longest_word(words):
# Build trie
root = {'#': ''} # '#' stores the word at this node
for w in words:
node = root
for ch in w:
node = node.setdefault(ch, {})
node['#'] = w
# BFS: only follow paths where every prefix is a word
queue = deque([root])
best = ''
while queue:
node = queue.popleft()
for key in sorted(node.keys()):
if key == '#':
continue
child = node[key]
if '#' in child: # this prefix is a valid word
if len(child['#']) > len(best):
best = child['#']
queue.append(child)
return best
# Test: longest_word(["w","wo","wor","worl","world"]) == "world"
# Test: longest_word(["a","banana","app","appl","ap","apply","apple"])
# == "apple" (same length as "apply", but lexicographically smaller)4 exercises: spot the signals, pick the method, avoid the trap.
Implement a trie with insert, search, and startsWith methods.
Signals
Build tree of characters. Insert walks/creates nodes. Search checks end flag. startsWith just walks. O(L) per op.
Store all words in a set (search is O(L)), but startsWith requires scanning all words.
Trap
Don't forget the `end_of_word` boolean flag — search and startsWith differ only by this check.
Design a data structure that supports adding words and searching with '.' wildcards that match any character.
Signals
Insert normally. On search, DFS when encountering '.', trying all children. O(26^dots * L) worst case.
Group words by length, brute-force match on '.' — slower for large dictionaries.
Trap
The '.' wildcard means you must try ALL children at that level — can't just follow one path.
Given a board of characters and a list of words, find all words that can be formed by adjacent cells.
Signals
Build trie from words. DFS from each cell, walking the trie simultaneously. Prune when no trie child. O(m*n*4^L).
For each word, backtrack on board. Works but repeats work across words. O(W*m*n*4^L).
Trap
Without the trie, you'd re-explore the board for each word. The trie lets you search all words in one traversal.
Given a list of words, find the longest word that can be built one character at a time by other words in the list.
Signals
Insert all words. BFS/DFS on trie, only following nodes where end=True. Longest path wins. O(sum of lengths).
Sort words. Use a set; only add word if word[:-1] is in the set. O(n log n + sum of lengths).
Trap
Don't just find the longest word — every prefix of the answer must also be a word in the list.
10 quick recall drills to reinforce this topic.
Same as search but returns True when you reach the end of the prefix — no need to check is_end.
def starts_with(root, prefix):
node = root
for ch in prefix:
if ch not in node.children:
return False
node = node.children[ch]
return TruePrefix search returns True if any word starts with the prefix. No end-flag check needed.
def starts_with(root, prefix):
node = root
for c in prefix:
if c not in node.children:
return False
node = node.children[c]
return TrueTrie insert walks/creates nodes per character, marks end. Search is identical but checks existence instead of creating.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
def insert(root, word):
node = root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = TrueWildcard '.' branches to all children. Without wildcards it's a straight walk — the DFS only fires on '.' characters.
def search(node, word, i=0):
if i == len(word):
return node.is_end
if word[i] == '.':
return any(search(ch, word, i+1)
for ch in node.children.values())
if word[i] not in node.children:
return False
return search(node.children[word[i]], word, i+1)Trie search checks end flag at the final node. Distinguishes full words from prefixes.
def search(root, word):
node = root
for c in word:
if c not in node.children:
return False
node = node.children[c]
return node.endGrid backtracking: mark cell as visited, explore 4 directions, unmark on backtrack. O(m*n*4^L).
def exist(board, word):
m, n = len(board), len(board[0])
def dfs(i, j, k):
if k == len(word): return True
if i < 0 or i >= m or j < 0 or j >= n: return False
if board[i][j] != word[k]: return False
tmp, board[i][j] = board[i][j], '#' # mark visited
for di, dj in (0,1),(0,-1),(1,0),(-1,0):
if dfs(i+di, j+dj, k+1): return True
board[i][j] = tmp # unmark
return False
for i in range(m):
for j in range(n):
if dfs(i, j, 0): return True
return FalseMove-zeroes is remove-element followed by a fill. Classic two-pointer warm-up.
w = 0
for r in range(len(a)):
if a[r] != 0:
a[w] = a[r]
w += 1
while w < len(a):
a[w] = 0
w += 1Write-pointer compaction for sorted arrays. Returns new length.
w = 1
for i in range(1, len(a)):
if a[i] != a[i-1]:
a[w] = a[i]
w += 1
return wDeque gives O(1) operations at both ends. Essential for BFS and sliding window.
from collections import deque
q = deque()
q.append(x)
q.popleft()BFS with implicit graph: each word connects to words differing by one letter. Try all 26 replacements at each position.
from collections import deque
def ladderLength(beginWord, endWord, wordList):
words = set(wordList)
if endWord not in words: return 0
q = deque([(beginWord, 1)])
visited = {beginWord}
while q:
word, steps = q.popleft()
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
nw = word[:i] + c + word[i+1:]
if nw == endWord: return steps + 1
if nw in words and nw not in visited:
visited.add(nw)
q.append((nw, steps + 1))
return 0