9. 单词搜索（JS实现）

1 题目
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用
示例:
board =
[
[‘A’,‘B’,‘C’,‘E’],
[‘S’,‘F’,‘C’,‘S’],
[‘A’,‘D’,‘E’,‘E’]
]
给定 word = “ABCCED”, 返回 true
给定 word = “SEE”, 返回 true
给定 word = “ABCB”, 返回 false
提示：
board 和 word 中只包含大写和小写英文字母。
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3

2 思路
这道题的思路主要还是考察深度优先遍历 + 回溯， 主要思路就是遍历二维数组每个元素，当发现元素和目标单词的首字母相同时，就进入递归，沿该元素的四个方向进行依次查找，用一个散列表标记已经访问过的位置，在递归过程中，若找到则返回true，若未找到，则递归回来时，要重置散列表状态

3代码
/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
var exist = function(board, word) {

let m = board.length;
let n = board[0].length;

if (m * n < word.length) return false;

let map = {};

for (let i=0; i<m; i++) {
for (let j=0; j<n; j++) {
if (board[i][j] === word[0]) {
if (search(i,j,0)) return true;
}
}
}

return false;

function search(i, j, nextIndex) {
//单词已遍历完，则表明已经找到了
if (nextIndex === word.length) {
return true;
};

let key = `${i}-${j}`;
//数组越界、已经访问过、对应字母不相等时直接返回false
if (i < 0 || j < 0 || i >= m || j >=n || map[key] || board[i][j] !== word[nextIndex]) {
return false;
}

map[key] = true;

let success = search(i+1, j, nextIndex + 1) //沿4个方向寻找
|| search(i-1, j, nextIndex + 1)
|| search(i, j+1, nextIndex + 1)
|| search(i, j-1, nextIndex + 1);

map[key] = success; //失败时要重置位置状态

return success;
}
};