NeetCode 150 · Tries

Tries Problems

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.
01 Medium Hash MapDesignTrie
Implement a trie with insert, search, and startsWith methods.
Test Cases
t = Trie() t.insert('apple') t.search('apple') → True t.search('app') → False t.startsWith('app') → True
dict childrenis_end flagO(m) per operation
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.
02 Medium TrieDFSDesign
Design a data structure that supports addWord and search. Search words can contain '.' which matches any letter.
Test Cases
wd = WordDictionary() wd.addWord('bad'); wd.addWord('dad'); wd.addWord('mad') wd.search('pad') → False wd.search('.ad') → True wd.search('b..') → True
trie DFS'.' wildcardO(26^m) worst
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).
03 Hard ArrayTrieBacktrackingMatrix
Given m×n board and list of strings words, return all words found in the board. Each cell can be used once per word.
Test Cases
board = [['o','a','a','n'],['e','t','a','e'],['i','h','k','r'],['i','f','l','v']] words = ['oath','pea','eat','rain'] findWords(board, words) → ['eat', 'oath']
Trie buildDFS backtrackingmark visited
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.
← Prev Category Next Category →