1268. Search Suggestions System
Tags:
Medium
Skills:
TrieBinary Search
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Đề bài yêu cầu xây dựng một hệ thống gợi ý tiềm kiếm giống như các thanh tìm kiếm trên các trang thương mại điện tử
Mô tả bài toán
- Bạn được cho một mảng các chuỗi products và một chuỗi searchWord
- Khi người dùng nhập từng ký tự của searchWord (từ trái → phải), sau mỗi ký tự, hệ thống sẽ gợi ý tối đa 3 sản phẩm từ products có tiền tố (prefix) trùng với phần đã nhập của searchWord
- Các sản phẩm gợi ý phải được sắp xếp theo thứ tự từ điển
- Nếu có nhiều hơn 3 sản phẩm phù hợp, chỉ lấy 3 sản phẩm đầu tiên theo thứ tự từ điển
Approach - Binary Search
- Sắp xếp mảng products theo thứ tự từ điển
- Duyệt từng ký tự của searchWord để tạo prefix
- Với mỗi prefix, tìm kiếm trong products các sản phẩm bắt đầu bằng prefix đó, lấy tối đa 3 sản phẩm đầu tiên
- Có thể dùng Binary Search để xác định vị trí bắt đầu của prefix trong mảng đã sắp xếp
- Sau đó, duyệt tiếp tối đa 3 phần từ để lấy các sản phẩm phù hợp
Time and space complexity - Binary Search
- TC: O(nlogn + mlogn): N là số lượng sản phẩm trong products, M là độ dài searchWord
- SC: O(M), độ dài searchWord
Solution - Binary search
typescripttypescript
1function suggestedProducts(products: string[], searchWord: string): string[][] {
2 products.sort();
3 const res: string[][] = [];
4 let prefix = "";
5
6 function lowerBound(arr: string[], target: string): number {
7 let left = 0;
8 let right = arr.length;
9 while (left < right) {
10 const mid = left + Math.floor((right - left) / 2);
11 if (arr[mid] < target) left = mid + 1;
12 else right = mid;
13 }
14 return left
15 }
16
17 for (let i = 0; i < searchWord.length; i++) {
18 prefix += searchWord[i];
19 const start = lowerBound(products, prefix);
20 const suggestions: string[] = [];
21
22 for (let j = start; j < Math.min(start + 3, products.length); j++) {
23 if (products[j].startsWith(prefix)) {
24 suggestions.push(products[j]);
25 } else {
26 break;
27 }
28 }
29
30 res.push(suggestions);
31 }
32
33 return res
34}💡
Tại sao console.log(”monitor” < “m”) là false?
Hiểu về cách JS so sách chuỗi
Javascript so sánh chuỗi theo thứ tự từ điển (lexicographical order) hay còn gọi là “dictionary order”. Khi so sánh hai chuỗi, JS sẽ so sánh từng ký tự một, từ trái → phải, cho đến khi tìm thấy sự khác biệt hoặc hết chuỗi
Thuật toán so sánh chuỗi trong JS hoạt động như sau
- So sánh ký tự đầu tiên của cả hai chuỗi
- Nếu ký tự đầu tiên khác nhau, chuỗi ký tự đầu tiên lớn hơn sẽ được coi là lớn hơn
- Nếu ký tự đầu tiên giống nhau, tiếp tục so sánh ký tự thứ hai
- Lặp lại cho đến khi tìm thấy sự khác biệt hoặc hết một trong hai chuỗi
- Nếu cả hai chuỗi có cùng độ dài và tất cả ký tự đều giống nhau, chúng được coi là bằng nhau
- Nếu một chuỗi là tiền tố của chuỗi kia (nghĩa là ngắn hơn và tất cả ký tự đều giống nhau), chuỗi dài hơn được coi là lớn hơn
typescripttypescript
1console.log("a" < "alpha"); // true, vì "a" là tiền tố của "alpha"
2console.log("apple" < "a"); // false, vì "a" là tiền tố của "apple"
3console.log("octo" < "okto"); // true, vì 'c' < 'k' trong bảng mã ASCIIApproach - Trie
- Xây dựng trie
- Mỗi node trong trie đại diện cho một ký tự
- Khi chèn từng sản phẩm vào Trie, node cuối cùng của mỗi sản phẩm sẽ đánh dấu là kết thúc từ
- Search suggestions
- Khi người dùng nhập từng ký tự của searchWord, duyệt theo Trie để đến node tương ứng với prefix
- Từ node này, thực hiện DFS để thu thập tối đa 3 sản phẩm (theo thứ tự từ điển) bắt đầu bằng prefix đó
Time and space complexity
- TC: O((N + S) * L)
- SC: O((N + S) * L)
- N là số lượng từ trong products
- L độ dài từ dài nhất
- S độ dài searchWord
Solution - Trie with DFS
typescripttypescript
1class TrieNode {
2 children: Array<TrieNode | null>;
3 isWord: boolean;
4
5 constructor() {
6 this.children = new Array(26).fill(null);
7 this.isWord = false;
8 }
9}
10
11class Trie {
12 root: TrieNode;
13 constructor() {
14 this.root = new TrieNode();
15 }
16
17 insert(word: string): void {
18 let node = this.root;
19 for (const char of word) {
20 const idx = char.charCodeAt(0) - 'a'.charCodeAt(0);
21 if (!node.children[idx]) {
22 node.children[idx] = new TrieNode();
23 }
24 node = node.children[idx]!;
25 }
26 node.isWord = true;
27 }
28
29 dfs(node: TrieNode, path: string, result: string[]): void {
30 if (result.length === 3) return;
31 if (node.isWord) result.push(path);
32
33 for (let i = 0; i < 26; i++) {
34 if (node.children[i]) {
35 const next_char = String.fromCharCode(i + 'a'.charCodeAt(0));
36 this.dfs(node.children[i]!, path + next_char, result);
37 if (result.length === 3) break;
38 }
39 }
40 }
41
42 getWordsStartingWith(prefix: string): string[] {
43 let node = this.root;
44 for (const char of prefix) {
45 const idx = char.charCodeAt(0) - 'a'.charCodeAt(0);
46 if (!node.children[idx]) return [];
47 node = node.children[idx]!;
48 }
49 const res: string[] = [];
50 this.dfs(node, prefix, res);
51 return res;
52 }
53}
54
55function suggestedProducts(products: string[], searchWord: string): string[][] {
56 const trie = new Trie();
57 for (const product of products) {
58 trie.insert(product);
59 }
60 const res: string[][] = [];
61 let prefix = "";
62 for (const char of searchWord) {
63 prefix += char;
64 res.push(trie.getWordsStartingWith(prefix));
65 }
66 return res;
67};