Trie Basics¶
Table of Contents¶
- 208. Implement Trie (Prefix Tree) (Medium)
- 211. Design Add and Search Words Data Structure (Medium)
- 14. Longest Common Prefix (Easy)
- 648. Replace Words (Medium)
- 677. Map Sum Pairs (Medium)
- 720. Longest Word in Dictionary (Medium)
- 1268. Search Suggestions System (Medium)
- 1233. Remove Sub-Folders from the Filesystem (Medium)
- 820. Short Encoding of Words (Medium)
- 2416. Sum of Prefix Scores of Strings (Hard)
- 2261. K Divisible Elements Subarrays (Medium)
- 1804. Implement Trie II (Prefix Tree) (Medium) 👑
- 2168. Unique Substrings With Equal Digit Frequency (Medium) 👑
208. Implement Trie (Prefix Tree)¶
"""
### Trie
- A trie is a tree-like data structure whose nodes store the letters of an alphabet.
"""
class TrieNode:
def __init__(self):
self.children = {}
self.endOfWord = None
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.endOfWord = True
def search(self, word: str) -> bool:
node = self.root
for c in word:
if c not in node.children:
return False
node = node.children[c]
return node.endOfWord
def startsWith(self, prefix: str) -> bool:
node = self.root
for c in prefix:
if c not in node.children:
return False
node = node.children[c]
return True
# Your Trie object will be instantiated and called as such:
obj = Trie()
obj.insert("apple")
print(obj.search("word")) # False
print(obj.startsWith("app")) # True
211. Design Add and Search Words Data Structure¶
class TrieNode:
def __init__(self):
self.children = {}
self.word = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word: str) -> None:
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.word = True
def search(self, word: str) -> bool:
def dfs(j, root):
node = root
for i in range(j, len(word)):
c = word[i]
if c == ".":
for child in node.children.values():
if dfs(i + 1, child):
return True
return False
else:
if c not in node.children:
return False
node = node.children[c]
return node.word
return dfs(0, self.root)
# Your WordDictionary object will be instantiated and called as such:
obj = WordDictionary()
obj.addWord("word")
print(obj.search("word"))
print(obj.search("w.rd"))
14. Longest Common Prefix¶
from typing import List
class longestCommonPrefix:
def horizontal_scan(self, strs: List[str]) -> str:
if not strs:
return ""
prefix = strs[0]
for i in range(1, len(strs)):
while not strs[i].startswith(prefix):
prefix = prefix[:-1]
if not prefix:
return ""
return prefix
def vertical_scan(self, strs: List[str]) -> str:
if not strs:
return ""
for i in range(len(strs[0])):
char = strs[0][i]
for j in range(1, len(strs)):
if i >= len(strs[j]) or strs[j][i] != char:
return strs[0][:i]
return strs[0]
def divide_conquer(self, strs: List[str]) -> str:
if not strs:
return ""
def merge(left, right):
n = min(len(left), len(right))
for i in range(n):
if left[i] != right[i]:
return left[:i]
return left[:n]
def find(strs, start, end):
if start == end:
return strs[start]
mid = start + (end - start) // 2
left = find(strs, start, mid)
right = find(strs, mid + 1, end)
return merge(left, right)
return find(strs, 0, len(strs) - 1)
def binary_search(self, strs: List[str]) -> str:
if not strs:
return ""
def isCommonPrefix(strs, length):
prefix = strs[0][:length]
return all(s.startswith(prefix) for s in strs)
minLen = min(len(s) for s in strs)
low, high = 0, minLen
while low < high:
mid = low + (high - low) // 2
if isCommonPrefix(strs, mid + 1):
low = mid + 1
else:
high = mid
return strs[0][:low]
if __name__ == "__main__":
solution = longestCommonPrefix()
strs = ["flower", "flow", "flight"]
assert solution.horizontal_scan(strs) == "fl"
assert solution.vertical_scan(strs) == "fl"
assert solution.divide_conquer(strs) == "fl"
assert solution.binary_search(strs) == "fl"