212. Word Search II
Tags:
Hard
Skills:
Trie
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
board) và một danh sách các từ (words)Approach - Backtracking & Trie
words vào Trie. Mỗi nút trong Trie sẽ lưu trữ một ký tự và thông tin về việc nó có phải là kết thúc của một từ hay khôngTime and space complexity
Solution - Trie & backtrack
1class TrieNode {
2 children: Map<string, TrieNode>;
3 is_end_word: boolean;
4
5 constructor() {
6 this.children = new Map();
7 this.is_end_word = false;
8 }
9}
10
11class Trie {
12 root: TrieNode;
13
14 constructor() {
15 this.root = new TrieNode();
16 }
17
18 insert(word: string): void {
19 let node = this.root;
20 for (const char of word) {
21 if (!node.children.has(char)) {
22 node.children.set(char, new TrieNode());
23 }
24 node = node.children.get(char)!;
25 }
26
27 node.is_end_word = true;
28 }
29
30 search(word: string): boolean {
31 let node = this.root;
32 for (const char of word) {
33 if (!node.children.has(char)) {
34 return false;
35 }
36 node = node.children.get(char)!;
37 }
38 return node.is_end_word;
39 }
40
41 startWith(prefix: string): boolean {
42 let node = this.root;
43 for (const char of prefix) {
44 if (!node.children.has(char)) {
45 return false;
46 }
47 node = node.children.get(char)!;
48 }
49 return true;
50 }
51}
52
53function findWords(board: string[][], words: string[]): string[] {
54 const trie = new Trie();
55
56 for (const word of words) {
57 trie.insert(word)
58 }
59
60 const res: Set<string> = new Set();
61 const rows = board.length;
62 const cols = board[0].length;
63 const directions = [
64 [-1, 0], [1, 0], [0, -1], [0, 1]
65 ]
66
67 function backtrack(node: TrieNode, i: number, j: number, path: string): void {
68 if (i < 0 || i >= rows || j < 0 || j >= cols || board[i][j] === "#") {
69 return;
70 }
71
72 const char = board[i][j];
73 if (!node.children.has(char)) return;
74
75 const next_node = node.children.get(char)!;
76 const new_path = path + char;
77
78 if (next_node.is_end_word) {
79 res.add(new_path);
80 next_node.is_end_word = false;
81 }
82
83 board[i][j] = "#"
84
85 for (const [dx, dy] of directions) {
86 const x = i + dx;
87 const y = j + dy;
88
89 backtrack(next_node, x, y, new_path)
90 }
91
92 board[i][j] = char;
93
94 if (next_node.children.size === 0) {
95 node.children.delete(char);
96 }
97 }
98
99 for (let i = 0; i < rows; i++) {
100 for (let j = 0; j < cols; j++) {
101 backtrack(trie.root, i, j, "");
102 }
103 }
104
105 return Array.from(res);
106};next_node.is_end_word = false; ?