A trie stores strings by their common prefixes. It's the go-to structure for prefix search, autocomplete, and word lookup problems.
Problems: 3
Easy: 0
Medium: 2
Hard: 1
Learning approach: Read the problem. Try the test cases yourself first.
Click Hint if stuck — it guides without spoiling.
Use Show Solution only after a genuine attempt.
Then hit Let's Code to run your solution live.
Each node is a dict of children and an is_end flag. insert/search/startsWith all walk the same character path.
Python Solution
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
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.root
for ch in word:
if ch not in node.children:
return False
node = node.children[ch]
return node.is_end
def startsWith(self, prefix):
node = self.root
for ch in prefix:
if ch not in node.children:
return False
node = node.children[ch]
return True
Key idea: Each node has a children dict and an is_end flag. All three operations traverse the same path character by character. The difference: search requires is_end=True; startsWith just needs to reach the end of the prefix.
Time: O(m) per operation where m is word length. Space: O(ALPHABET × N) for N words.
Build a trie for addWord. For search, DFS and handle '.' by trying all children.
Python Solution
class WordDictionary:
def __init__(self):
self.root = {}
def addWord(self, word):
node = self.root
for ch in word:
if ch not in node:
node[ch] = {}
node = node[ch]
node['#'] = True # end marker
def search(self, word):
def dfs(node, i):
if i == len(word):
return '#' in node
ch = word[i]
if ch == '.':
return any(dfs(node[c], i + 1) for c in node if c != '#')
if ch not in node:
return False
return dfs(node[ch], i + 1)
return dfs(self.root, 0)
Key idea: Standard trie for addWord. For search, DFS handles '.' by trying every child branch. The '#' key marks word endings.
Time: O(m) add, O(26^m) search worst case for all-dot patterns. Space: O(ALPHABET × N).
Build a trie from the word list. DFS from every cell, pruning paths not in the trie. Mark cells as visited during DFS.
Python Solution
def findWords(board, words):
# Build trie from word list
trie = {}
for word in words:
node = trie
for ch in word:
node = node.setdefault(ch, {})
node['$'] = word # store word at end node
rows, cols = len(board), len(board[0])
result = set()
def dfs(r, c, node):
ch = board[r][c]
if ch not in node:
return
next_node = node[ch]
if '$' in next_node:
result.add(next_node['$'])
board[r][c] = '#' # mark visited
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != '#':
dfs(nr, nc, next_node)
board[r][c] = ch # restore
for r in range(rows):
for c in range(cols):
dfs(r, c, trie)
return list(result)
Key idea: Build a trie for fast prefix pruning. DFS from every board cell. The trie prunes paths that don't lead to any word. Mark visited cells with '#' and restore on backtrack.
Time: O(M · 4 · 3^(L-1)) where M=cells, L=max word length. Space: O(W·L) for the trie.