-
Notifications
You must be signed in to change notification settings - Fork 7
/
WordSearch.js
33 lines (32 loc) · 1.09 KB
/
WordSearch.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
var exist = function (board, word) {
for (let x = 0; x < board.length; x++) {
for (let y = 0; y < board[0].length; y++) {
if (board[x][y] != word[0]) continue;
let visited = Array(board.length);
for (let i = 0; i < visited.length; i++)
visited[i] = [];
if (dfs(board, word, visited, x, y, 0))
return true;
}
}
return false;
};
var dfs = function (board, word, visited, x, y, index) {
if (index == word.length)
return true;
if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || visited[x][y] || board[x][y] != word[index])
return false;
visited[x][y] = true;
var res = false;
res = res || dfs(board, word, visited, x + 1, y, index + 1);
res = res || dfs(board, word, visited, x - 1, y, index + 1);
res = res || dfs(board, word, visited, x, y + 1, index + 1);
res = res || dfs(board, word, visited, x, y - 1, index + 1);
visited[x][y] = false;
return res;
}