208. Implement Trie (Prefix Tree)
Design, Trie, Hash Table, String ·Problem Statement
link: https://leetcode.com/problems/implement-trie-prefix-tree/ https://leetcode.cn/problems/implement-trie-prefix-tree/
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: ["Trie", "insert", "search", "search", "startsWith", "insert", "search"][[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output: [null, null, true, false, true, null, true]
Solution Approach
Use nested dictionaries to represent trie nodes for efficient operations.
Algorithm
- Initialization: Start with an empty root dictionary.
- Insertion: Traverse the word in the trie, creating new nodes as needed. Mark end of word with ‘#’.
- Search: Check for word’s presence; if missing any character or missing end-of-word marker, return False.
- StartsWith: Traverse using the prefix; if any character is missing, return False.
Implement
class Trie:
def __init__(self):
self.dic = {}
def insert(self, word: str) -> None:
cur = self.dic
for c in word:
if c not in cur:
cur[c] = {}
cur = cur[c]
cur['#'] = True
def search(self, word: str) -> bool:
cur = self.dic
for c in word:
if c not in cur:
return False
cur = cur[c]
return '#' in cur
def startsWith(self, prefix: str) -> bool:
cur = self.dic
for c in prefix:
if c not in cur:
return False
cur = cur[c]
return True