LeetCode: Trees II 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.
Pseudocode
text will go here
Solution 1: Recursive Trie Implementation - Trie/Trie Insert and Search Recursive
class TrieNode:
def __init__(self):
# list of continuing letters (subtrees) for node: char -> TrieNode
self.subtrees = {}
# marks current node as valid end of word
self.is_end = False
class Trie:
def __init__(self):
# Root node does not store any chars itself
self.root = TrieNode()
# Recursive Insert
# tc: O(n), word length
# sc: O(n), node creation
def insert(self, word: str) -> None:
def dfs_insert(node: TrieNode, i: int):
# Base case: finished word
if i == len(word):
node.is_end = True
return
c = word[i]
if c not in node.subtrees:
node.subtrees[c] = TrieNode()
# Recurse to next letter
dfs_insert(node.subtrees[c], i + 1)
dfs_insert(self.root, 0)
# Recursive Search
# tc: O(n), word length
# sc: O(n), recursion stack
def search(self, word: str) -> bool:
def dfs_search(node: TrieNode, i: int) -> bool:
# Base case: finished word
if i == len(word):
return node.is_end
c = word[i]
if c not in node.subtrees:
return False
# Recurse to next letter
return dfs_search(node.subtrees[c], i + 1)
return dfs_search(self.root, 0)
# Recursive StartsWith
# tc: O(n), prefix length
# sc: O(n), recursion stack
def startsWith(self, prefix: str) -> bool:
def dfs_startsWith(node: TrieNode, i: int) -> bool:
# Base case: finished prefix
if i == len(prefix):
return True
c = prefix[i]
if c not in node.subtrees:
return False
# Recurse to next letter
return dfs_startsWith(node.subtrees[c], i + 1)
return dfs_startsWith(self.root, 0)
# overall: tc O(n) per operation
# overall: sc O(n) per operation (recursion stack)Solution 2: Iterative Trie Implementation - Trie/Trie Insert and Search Recursive
class TrieNode:
# TrieNode:
# We need to track
# - subtrees for current node (letters current letter can continue to)
# - if current node represents the valid end of a node
# For our functions, they may need to update the above 2 details
# Insert():
# - Insert a new word into the trie tree
# - Add letters to existing trie nodes
# Search():
# - Check if a word exists in the trie tree
# - Travel down trie nodes to verify word exists
# StartsWith():
# - Check if a word exists in the trie tree that has a prefix
# - Travel down trie node to verify prefix, and then continue to
# verify if any word uses it
def __init__(self):
# list of continuing letters (subtrees) for node: char -> TrieNode
self.subtrees = {}
# marks current node as valid end of word
self.is_end = False
class Trie:
def __init__(self):
# Root node:
# Does not store any chars itself,
# only points to its child char nodes
self.root = TrieNode()
# tc: iterate over word of length n O(n)
# sc: subtree node creation for n nodes O(n)
def insert(self, word: str) -> None:
# start search at root
node = self.root
# Insert each letter of word into trie tree in correct order
for c in word:
# if subtree does not exist for current letter, add to list
if c not in node.subtrees:
node.subtrees[c] = TrieNode()
# iterate to next letter node
node = node.subtrees[c]
# finished adding all chars to trie tree, mark last char
# as valid end to a word
node.is_end = True
# tc:
# sc:
def search(self, word: str) -> bool:
# Return True only if final node is valid end
# start at root
node = self.root
# Traverse the trie using words char
# tc: iterate over word length n O(n)
for c in word:
# if subtree does not exist, word path is not in trie
if c not in node.subtrees:
return False
# iterate to next letter node
node = node.subtrees[c]
# check if last char is valid end of a word
return node.is_end
# tc:
# sc:
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: tc
# overall: sc211. 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 word functionality.
Pseudocode
text will go here
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()
# tc:
# sc:
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
# tc:
# sc:
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: tc
# overall: sc