LeetCode: Tries
Trie Intro
LeetCode questions regarding tries.
What is a Trie
A Trie, also known as a prefix tree, is a tree data structure used for storing and querying strings (words) efficiently
Trie Characteristics
Tries are a special type of tree, characterized by:
- Nodes: Each node stores a character
- Edges: Represent transitions from one character to the next
- Root: Represents an empty string prefix
- Word End Flag: Nodes mark the end of a valid word via a boolean or by storing the complete word
- Subtrees: Nodes can have multiple children, one per possible next character.
- No Cycles: Tries are acyclic graphs
- Time and Space Tradeoff: Space complexity can be large O(sum of all chars), but allows for efficient prefix queries O(1) ** check this **
- Alphabet Size: Can be optimized based on the expected character set (26 for lowercase English)
Trie Representation
Tries are usually represented in TrieNodes which hold a dictionary of char -> subtrees.
Trie IRL
Autocomplete Systems: Find all words starting with a given prefix
Spell Checkers: Quickly find if a word exists or suggest corrections
Prefix Matching: Search for all strings sharing a common prefix
IP Routing: Longest prefix matching in networking
Word Games: Efficiently verify and search word lists
Trie Visualization
Example words inserted: ["cat", "car", "dog"]
root
/ \
c d
/ \
a o
/ \ \
t r g
(end) (end) (end)Trie Application: Trie Insert and Search Recursive
Traversal Order: Insert/Search characters one by one from root to leaf nodes Mindset: At each char, check subtrees and create new nodes if needed (insert) or check existence (search) Trick: Ill follow the string one char at a time, building or verifying the path as I go
Ex: Basic Trie Insert and Search Recursive
class TrieNode:
def __init__(self):
# Children dictionary: char -> TrieNode
self.children = {}
# Indicates if node marks end of a valid word
self.is_end_of_word = False
class Trie:
def __init__(self):
# Root node represents empty prefix
self.root = TrieNode()
def insert(self, word: str) -> None:
def insert_recursive(node: TrieNode, idx: int):
# Note:
# Base case: if index reached end of word, mark node as word end
if idx == len(word):
node.is_end_of_word = True
return
ch = word[idx]
# If no child node for current char, create one
if ch not in node.children:
node.children[ch] = TrieNode()
# Recursive call to next character
insert_recursive(node.children[ch], idx + 1)
# Start recursive insertion at root and index 0
insert_recursive(self.root, 0)
def search(self, word: str) -> bool:
def search_recursive(node: TrieNode, idx: int) -> bool:
# Note:
# Base case: if index reached end, check if current node marks end of a word
if idx == len(word):
return node.is_end_of_word
ch = word[idx]
# If character path missing, word does not exist
if ch not in node.children:
return False
# Recursive call to next character
return search_recursive(node.children[ch], idx + 1)
# Start recursive search at root and index 0
return search_recursive(self.root, 0)
# ["cat", "car", "dog"]:
# root
# / \
# c d
# / \
# a o
# / \ \
# t r g
# (end) (end) (end)208. Implement Trie (Prefix Tree) ::1:: - Medium
Topics: Hash Table, String, Design, Trie
Intro
A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker. Implement the Trie class: Trie() Initializes the trie object. void insert(String word) Inserts the string word into the trie. boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise. boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.
| Example Input | Output |
|---|---|
| ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]] | [null, null, true, false, true, null, true] |
Constraints:
1 ≤ word.length, prefix.length ≤ 2000
word and prefix consist only of lowercase English letters.
At most 3 * 104 calls in total will be made to insert, search and starts with
Abstraction
Implement a trie data structure.
Space & Time Complexity
| Solution | Time Complexity | Space Complexity | Time Remark | Space Remark |
|---|---|---|---|---|
| Bug | Error |
|---|---|
Brute Force:
| Aspect | Time Complexity | Space Complexity | Time Remarks | Space Remarks |
|---|---|---|---|---|
Find the Bug:
Solution 1: Trie Implementation - Trie/Trie Insert and Search Recursive
class TrieNode:
def __init__(self):
# list of char subtrees for current node: char -> TrieNode
self.subtrees = {}
# Indicates end of a valid word
self.is_end = False
class Trie:
def __init__(self):
# Note:
# root node does not store any chars itself,
# it only points to child chars
self.root = TrieNode()
# time complexity:
# space complexity:
def insert(self, word: str) -> None:
# Note:
# Insert word char by char into the trie
# If a char path does not exist, create a new TrieNode
# start search at root
node = self.root
# insert each char
for c in word:
# if subtree does not exist, create new
if c not in node.subtrees:
node.subtrees[c] = TrieNode()
# iterate to subtree
node = node.subtrees[c]
# mark last char
node.is_end = True
# time complexity:
# space complexity:
def search(self, word: str) -> bool:
# Note:
# Traverse the trie following each character
# Return True only if final node marks end of a valid word
# start at root
node = self.root
# for each char
for c in word:
# if subtree does not exist, work is not in trie
if c not in node.subtrees:
return False
# iterate to subtree
node = node.subtrees[c]
# check if valid end of word
return node.is_end
# time complexity:
# space complexity:
def startsWith(self, prefix: str) -> bool:
# Note:
# Similar to search(), but only checks if prefix path exists
# No need to check is_end flag
# start at root
node = self.root
# for each char
for c in prefix:
# if subtree does not exist, false
if c not in node.subtrees:
return False
# iterate to subtree
node = node.subtrees[c]
# entire prefix exists, true
return True
# overall: time complexity
# overall: space complexity211. Design Add and Search Words Data Structure ::1:: - Medium
Topics: String, Depth First Search, Design, Trie
Intro
Design a data structure that supports adding new words and finding if a string matches any previously added string. Implement the WordDictionary class: WordDictionary() Initializes the object. void addWord(word) Adds word to the data structure, it can be matched later. bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.
| Example Input | Output |
|---|---|
| ["WordDictionary","addWord","addWord","addWord","search","search","search","search"] [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]] | [null,null,null,null,false,true,true,true] |
Constraints:
1 ≤ word.length, prefix.length ≤ 25
word in addWord consists of lowercase English letters.
word in search consist of '.' or lowercase English letters.
There will be at most 2 dots in word for search queries.
At most 104 calls will be made to addWord and search.
Abstraction
Implement a trie data structure with add work functionality.
Space & Time Complexity
| Solution | Time Complexity | Space Complexity | Time Remark | Space Remark |
|---|---|---|---|---|
| Bug | Error |
|---|---|
Brute Force:
| Aspect | Time Complexity | Space Complexity | Time Remarks | Space Remarks |
|---|---|---|---|---|
Find the Bug:
Solution 1: Trie Implementation - Trie/Trie Insert and Search Recursive
class TrieNode:
def __init__(self):
# list of char subtrees for current node: char -> TrieNode
self.subtrees = {}
# Indicates end of a valid word
self.is_end = False
class WordDictionary:
def __init__(self):
# Note:
# root node does not store any chars itself,
# it only points to child chars
self.root = TrieNode()
# time complexity:
# space complexity:
def addWord(self, word: str) -> None:
# Note:
# Inserts a word into the trie character-by-character.
# Creates new TrieNodes if a character path does not exist.
# start at root
node = self.root
# for each char
for c in word:
# if subtree does not exist, create
if c not in node.subtrees:
node.subtrees[c] = TrieNode()
# iterate to subtree
node = node.subtrees[c]
# mark valid end of word
node.is_end = True
# time complexity:
# space complexity:
def search(self, word: str) -> bool:
# Note:
# In previous trie, all searches are deterministic
# Here due to wildcard '.', we must try all possible subtree paths
# and stop early if a match is found.
def dfs(index: int, node: TrieNode) -> bool:
# Base case: check if valid end of word
if index == len(word):
return node.is_end
# grab curr char
c = word[index]
# non deterministic: search all subtrees
if c == '.':
# try all subtree paths
for child_node in node.subtrees.values():
# early exit if match is found
if dfs(index + 1, child_node):
return True
# explored all paths, string does not exist
return False
# deterministic: check if subtree exists
else:
# char subtree does not exist
if c not in node.subtrees:
return False
# continue down char subtree
return dfs(index + 1, node.subtrees[c])
return dfs(0, self.root)
# overall: time complexity
# overall: space complexity212. Word Search II ::2:: - Hard
Topics: Hash Table, String, Design, Trie
Intro
Given an m x n board of characters and a list of strings words, return all words on the board. Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
| Example Input | Output |
|---|---|
| look at LeetCode question diagram | ["eat","oath"] |
Constraints:
m == board.length
n == board[i].length
1 ≤ m, n ≤ 12
board[i][j] is a lowercase English letter.
1 ≤ words.length ≤ 3 * 104
1 ≤ works[i].length ≤ 10
words[i] consists of lowercase English letters.
All the strings of words are unique.
Abstraction
Given a board and a list of words, return all words from the list that are present on the board.
Space & Time Complexity
| Solution | Time Complexity | Space Complexity | Time Remark | Space Remark |
|---|---|---|---|---|
| Bug | Error |
|---|---|
Brute Force:
| Aspect | Time Complexity | Space Complexity | Time Remarks | Space Remarks |
|---|---|---|---|---|
Find the Bug:
Solution 1: Trie Implementation - Trie/Trie Insert and Search Recursive
class TrieNode:
def __init__(self):
# list of char subtrees for current node: char -> TrieNode
self.subtrees = {}
# Indicates end of a valid word
self.isWord = False
# time complexity:
# space complexity:
def addWord(self, word):
# updated current node
node = self
# for each char
for c in word:
# if subtree does not exist, create
if c not in node.subtrees:
node.subtrees[c] = TrieNode()
# iterate to subtree
node = node.subtrees[c]
# set as valid end of word
node.isWord = True
class Solution:
# time complexity:
# space complexity:
def findWords(self, board, words):
# Note:
# 1. We build a Trie from the provided word list for O(1) prefix checking
# 2. DFS from each cell to explore all possible words
# 3. Mark visited cells in place by temporarily replacing char with '#'
# to avoid using extra memory for tracking visited cells
# 4. Once word is found, add to results and remove from Trie (set node.Word=None)
# to prevent duplicate matches
# 5. Prune Trie nodes by removing leaf nodes to reduce unnecessary DFS branches
# build Trie for provided words
root = TrieNode()
for word in words:
root.addWord(word)
# board boundaries
rows, cols = len(board), len(board[0])
# tracking
res, visit = set(), set()
def dfs(r, c, node, path):
# Boundary check and pruning:
# check board boundaries
if r < 0 or c < 0 or r >= rows or c >= cols:
return
# curr board char exists in Trie subtrees of node
if board[r][c] not in node.subtrees:
return
# curr cell has already been visited to avoid reuse
if (r, c) in visit:
return
# Not yet visited, continue dfs
# add to visited
visit.add((r, c))
# grab subtrees
node = node.subtrees[board[r][c]]
# track char path
path += board[r][c]
# check if valid end of word
if node.isWord:
res.add(path)
# dfs: up, down, left, and left from current node
for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
dfs(r + dr, c + dc, node, path)
# remove from curr node from visited
visit.remove((r, c))
# explore each cell in grid
for r in range(rows):
for c in range(cols):
# explore current cell
dfs(r, c, root, "")
# overall: time complexity
# overall: space complexity
return list(res)Solution 2: Trie Implementation Optimal - Trie/Trie Insert and Search Recursive
class TrieNode:
def __init__(self):
# list of char subtrees for current node: char -> TrieNode
self.subtrees = {}
# store complete word at end node, None if not end
self.word = None
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
# Note:
# 1. Build a Trie from the given word list for O(1) prefix checking.
# 2. DFS from each cell to explore all possible words
# 3. Mark visited cells in place by temporarily replacing char with '#'
# 4. Once word is found, add to results and remove from Trie (set node.Word=None)
# to prevent duplicate matches
# 5. Prune Trie nodes by removing leaf nodes to reduce unnecessary DFS branches
# build Trie for provided words
root = TrieNode()
for word in words:
node = root
for c in word:
# if subtree does not exist, create
if c not in node.subtrees:
node.subtrees[c] = TrieNode()
# iterate to subtree
node = node.subtrees[c]
# add word to end of list
node.word = word
# grid boundaries
rows, cols = len(board), len(board[0])
# res
result = []
def backtrack(r: int, c: int, parent: TrieNode):
# grab curr char
letter = board[r][c]
# grab node for curr char
curr_node = parent.subtrees[letter]
# if valid end of word
if curr_node.word:
result.append(curr_node.word)
# remove word to avoid duplicates
curr_node.word = None
# mark the cell as visited
board[r][c] = "#"
# dfs: up, down, left, and right from curr node
for (dr, dc) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
# new rows and columns
(nr, nc) = r + dr, c + dc
# ignore dfs if invalid
if (0 <= nr < rows and
0 <= nc < cols and
board[nr][nc] in curr_node.subtrees):
backtrack(nr, nc, curr_node)
# restore cell (unvisited)
board[r][c] = letter
# Optimization:
# Remove leaf node to prune search space
# if char has no more subtrees, remove from search space
# (which will prune as we return recursively)
if not curr_node.subtrees:
parent.subtrees.pop(letter)
# dfs from all cells
for r in range(rows):
for c in range(cols):
# for curr cell
if board[r][c] in root.subtrees:
backtrack(r, c, root)
# overall: time complexity
# overall: space complexity
return result