DSAÝ tưởng: Mỗi node giữ một map con (theo ký tự) và cờ isEnd đánh dấu kết thúc một từ. insert đi xuống tạo node theo từng ký tự; search/startsWith đi theo đường dẫn ký tự.
Khi nào dùng Trie vs HashSet: HashSet tìm đúng một từ O(L) là đủ. Trie thắng khi cần truy vấn theo tiền tố (autocomplete, startsWith) hoặc duyệt nhiều từ chung prefix — HashSet không làm được tiền tố hiệu quả.
class TrieNode { children: Record<string, TrieNode> = {}; isEnd = false }
class Trie {
private root = new TrieNode()
insert(word: string): void {
let node = this.root
for (const ch of word) (node.children[ch] ??= new TrieNode(), node = node.children[ch])
node.isEnd = true
}
private find(word: string): TrieNode | null {
let node = this.root
for (const ch of word) { if (!node.children[ch]) return null; node = node.children[ch] }
return node
}
search(word: string): boolean { return this.find(word)?.isEnd ?? false }
startsWith(prefix: string): boolean { return this.find(prefix) !== null }
}Độ phức tạp: insert/search/startsWith đều O(L) với L = độ dài từ; bộ nhớ O(tổng số ký tự).
Lưu ý: search khác startsWith ở chỗ phải kiểm tra isEnd — "app" có trong cây không có nghĩa nó là một từ hoàn chỉnh.
Idea: Each node holds a child map (keyed by character) and an isEnd flag marking a word's end. insert walks down creating nodes per character; search/startsWith follow the character path.
Trie vs HashSet: A HashSet finding one exact word in O(L) is enough. The Trie wins for prefix queries (autocomplete, startsWith) or traversing many words sharing a prefix — HashSet can't do prefixes efficiently.
class TrieNode { children: Record<string, TrieNode> = {}; isEnd = false }
class Trie {
private root = new TrieNode()
insert(word: string): void {
let node = this.root
for (const ch of word) (node.children[ch] ??= new TrieNode(), node = node.children[ch])
node.isEnd = true
}
private find(word: string): TrieNode | null {
let node = this.root
for (const ch of word) { if (!node.children[ch]) return null; node = node.children[ch] }
return node
}
search(word: string): boolean { return this.find(word)?.isEnd ?? false }
startsWith(prefix: string): boolean { return this.find(prefix) !== null }
}Complexity: insert/search/startsWith all O(L) where L = word length; space O(total characters).
Note: search differs from startsWith by checking isEnd — "app" existing in the tree doesn't mean it's a complete word.