211. Design Add and Search Words Data Structure
Tags:
Medium
Skills:
Trie
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu thiết kết một cấu trúc dữ liệu hỗ trợ 2 thao tác:
- addWord(word): Thêm một từ vào cấu trúc dữ liệu
- search(word): Tìm kiếm từ trong cấu trúc dữ liệu, trong đó ký tự
.có thể đại diện cho bất kỳ chữ cái nào
Cách tiếp cận tối ưu là sử dụng trie để lưu trữ các từ vì
- Trie cho phép chèn từ và tìm kiếm từ với độ phức tạp tuyến tính theo độ dài từ
- Khi găp ký tự
.ta cần thử các nhánh con tại vị trí đó (DFS)
Approach
- Mỗi node trong Trie lưu
- Một map các ký tự con (children)
- Một flag đánh dấu kết thúc từ (is_end_of_word)
- Khi thêm từ, duyệt từng ký tự, tạo node nếu chưa có
- Khi tìm kiếm, nếu gặp
.thử đệ quy tất cả các nhánh con tại vị trí đó, nếu là ký tự thường thì đi tiếp xuống nhánh tương ứng
Time and space complexity
- L: Độ dài từ dài nhất
- N: Số lượng từ đã thêm vào
Solution
typescripttypescript
1class TrieNode {
2 children: Map<string, TrieNode>;
3 is_end_of_word: boolean;
4 constructor() {
5 this.children = new Map();
6 this.is_end_of_word = false;
7 }
8}
9
10class WordDictionary {
11 root: TrieNode;
12
13 constructor() {
14 this.root = new TrieNode();
15 }
16
17 addWord(word: string): void {
18 let node = this.root;
19 for (const char of word) {
20 if (!node.children.has(char)) {
21 node.children.set(char, new TrieNode());
22 }
23 node = node.children.get(char)!;
24 }
25 node.is_end_of_word = true;
26 }
27
28 search(word: string): boolean {
29 function dfs(node: TrieNode, index: number): boolean {
30 if (index === word.length) {
31 return node.is_end_of_word;
32 }
33
34 const char = word[index];
35 if (char === '.') {
36 for (const child of node.children.values()) {
37 if (dfs(child, index + 1)) return true;
38 }
39 return false;
40 } else {
41 const next_node = node.children.get(char);
42 if (!next_node) return false;
43 return dfs(next_node, index + 1)
44 }
45 }
46 return dfs(this.root, 0);
47 }
48}
49
50/**
51 * Your WordDictionary object will be instantiated and called as such:
52 * var obj = new WordDictionary()
53 * obj.addWord(word)
54 * var param_2 = obj.search(word)
55 */💡
Giải thích về hàm
searchNguyên lý hoạt động
- Duyệt qua từng ký tự của từ cần tìm
- Nếu ký tự là chữ cái thông thường, kiểm tra xem node con tương ứng có tồn tại không, nếu không thì return về
false - Nếu ký tự là dấu chấm
., đây là wildcard phải thử tất cả các node con tại vị trí đó (đệ quy xuống từng nhánh con) - Khi duyệt hết toàn bộ ký tự, kiểm tra node hiện tại có phải là kết thúc của một từ hợp lệ hay không