Build and Search
208. Implement Trie (Prefix Tree)
Medium·
Fixed 26-Slot Child Array
O(L) timeO(26 * n * L) aux
FIG. IMPLEMENT TRIE PREFIX TREE● INTERACTIVE
visualization loads as you reach it
class TrieNode:
def __init__(self):
self.count = 0
self.children = [None] * 26
self.end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
curr = self.root
getIndex = lambda char: ord(char) - ord("a")
for char in word:
if not curr.children[getIndex(char)]:
curr.children[getIndex(char)] = TrieNode()
curr = curr.children[getIndex(char)]
curr.count += 1
curr.end = True
def search(self, word: str) -> bool:
curr = self.root
getIndex = lambda char: ord(char) - ord("a")
for char in word:
if not curr.children[getIndex(char)]:
return False
curr = curr.children[getIndex(char)]
return curr.end == True
def startsWith(self, prefix: str) -> bool:
curr = self.root
getIndex = lambda char: ord(char) - ord("a")
for char in prefix:
if not curr.children[getIndex(char)]:
return False
curr = curr.children[getIndex(char)]
return True
def __str__(self) -> str:
def walk(node, depth):
for i, child in enumerate(node.children):
if child:
mark = "*" if child.end else ""
lines.append(f"{' ' * depth}{chr(i + 97)}{mark} ({child.count})")
walk(child, depth + 1)
lines = []
walk(self.root, 0)
return "\n".join(lines) or "<empty>"
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)
211. Design Add and Search Words Data Structure
Medium·
Wildcard Recursion over Dict Children
O(n * L^2) timeO(n * L + L^2) aux
FIG. DESIGN ADD AND SEARCH WORDS DATA STRUCTURE● INTERACTIVE
visualization loads as you reach it
class TrieNode:
def __init__(self):
self.count = 0
self.children = {}
self.end = False
def getChildren(self):
for c in self.children.values():
yield c
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word: str) -> None:
curr = self.root
for char in word:
curr = curr.children.setdefault(char, TrieNode())
curr.count += 1
curr.end = True
def search(self, word: str) -> bool:
def rec(node, word):
if not word:
return node.end
char, next_word = word[0], word[1:]
if char == ".":
for c in node.getChildren():
if rec(c, next_word):
return True
return False
child = node.children.get(char, None)
return rec(child, next_word) if child else False
return rec(self.root, word)
# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)
720. Longest Word in Dictionary
Medium·
DFS the Trie, Stopping at the First Gap
O(n * L + n * L^2) timeO(n * L + n * L^2) aux
FIG. LONGEST WORD IN DICTIONARY● INTERACTIVE
visualization loads as you reach it
class TrieNode:
def __init__(self):
self.count = 0
self.children = {}
self.end = 0
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
curr = self.root
for char in word:
curr = curr.children.setdefault(char, TrieNode())
curr.count += 1
curr.end = True
def __str__(self) -> str:
lines = []
def walk(node, depth):
for char, child in sorted(node.children.items()):
mark = "*" if child.end else ""
lines.append(f"{' ' * depth}{char}{mark} ({child.count})")
walk(child, depth + 1)
walk(self.root, 0)
return "\n".join(lines) or "<empty>"
class Solution:
def longestWord(self, words: list[str]) -> str:
trie = Trie()
for word in words:
trie.insert(word)
maxi = 0
maxi_words = []
def dfs(node, word):
nonlocal maxi, maxi_words
if not node.end:
return
if maxi < len(word):
maxi = len(word)
maxi_words = []
if maxi == len(word):
maxi_words.append(word)
for child_char, child in node.children.items():
dfs(child, word + child_char)
for child_char, child in trie.root.children.items():
dfs(child, child_char)
if not maxi_words:
return ""
return min(maxi_words)