1
/**
2
 * @param {character[][]} board
3
 * @param {string} word
4
 * @return {boolean}
5
 */
6

7
let visited;
8

9
const getNeighbours = ([i, j], board) => {
10
  let arr = [];
11
  if (i > 0 && !visited[i - 1][j]) arr.push([i - 1, j]);
12
  if (j > 0 && !visited[i][j - 1]) arr.push([i, j - 1]);
13
  if (i + 1 < board.length && !visited[i + 1][j]) arr.push([i + 1, j]);
14
  if (j + 1 < board[i].length && !visited[i][j + 1]) arr.push([i, j + 1]);
15
  return arr;
16
};
17
const dfs = ([i, j], board, word, index) => {
18
  if (word[index] !== board[i][j]) return false;
19
  if (word.length - 1 === index) return true;
20
  visited[i][j] = true;
21
  let neighbours = getNeighbours([i, j], board, word, index) || [];
22

23
  for (let k = 0; k < neighbours.length; k++) {
24
    let temp_result = dfs(neighbours[k], board, word, index + 1);
25
    if (temp_result === true) return true;
26
  }
27
  visited[i][j] = false;
28
  return false;
29
};
30

31
var exist = function (board, word) {
32
  visited = [];
33
  for (let i = 0; i < board.length; i++) {
34
    visited[i] = [];
35
    for (let j = 0; j < board[i].length; j++) {
36
      visited[i][j] = false;
37
    }
38
  }
39
  for (let i = 0; i < board.length; i++) {
40
    for (let j = 0; j < board[i].length; j++) {
41
      if (board[i][j] === word[0]) {
42
        let result = dfs([i, j], board, word, 0);
43
        if (result === true) return true;
44
      }
45
    }
46
  }
47

48
  return false;
49
};