79. Word Search
Tags:
Medium
Skills:
Matrixbacktrack
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 kiểm tra xem một từ word có thể được tạo thành từ các ký tự liền kề trong một bảng ký tự 2 chiều board hay không. Mỗi ký tự trong bảng chỉ được dùng một lần cho mỗi lần kiểm tra. Các ký tự liền kề 4 hướng: lên, xuống, trái, phải (không chéo)
Approach
true . Nếu không tìm được, return false truefalse Time and space complexity
Solution
1function exist(board: string[][], word: string): boolean {
2 const rows = board.length;
3 const cols = board[0].length;
4 const dirs = [
5 [-1, 0], [1, 0], [0, 1], [0, -1]
6 ]
7
8 function dfs(i: number, j: number, k: number): boolean {
9 if (k === word.length) return true;
10 if (i < 0 || i >= rows || j < 0 || j >= cols || board[i][j] !== word[k]) {
11 return false
12 }
13
14 let temp = board[i][j];
15 board[i][j] = '#'
16
17 let found = false;
18 for (const [dx, dy] of dirs) {
19 if (dfs(dx + i, dy + j, k + 1)) {
20 found = true
21 }
22 }
23
24 board[i][j] = temp;
25
26 return found;
27 }
28
29 for (let i = 0; i < rows; i++) {
30 for (let j = 0; j < cols; j++) {
31 if (dfs(i, j, 0)) {
32 return true;
33 }
34 }
35 }
36
37 return false;
38};dfs sẽ kiểm tra từng ký tự của từ, nếu trùng thì tiếp tục đệ quy sang các ô lân cậnk và word ?k là chỉ số của ký tự hiện tại trong từ word.k bằng word.length - 1, nghĩa là bạn vừa kiểm tra xong ký tự cuối cùng, nếu nó đúng thì đã tìm được từ.word.length === k, tức là bạn phải kiểm tra thêm một ký tự ngoài phạm vi của từ, điều này không đúng.