# 0079. Word Seach

## 刷题内容

• https://leetcode-cn.com/problems/word-search/

 board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]

给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.


## 解题方案

/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
var exist = function(board, word) {
let height = board.length;
let width = board[0].length;
let result = false;
for(let x = 0; x < height; x++) {
for(let y = 0; y < width; y++) {
if (board[x][y] === word[0]) {
result = result || searchDFS(board, [ x, y ], shiftWord(word), [[x,y]])
}
}
}
return result;
};

var searchDFS = function (board, [x,y], word, useList = []) {
const list = [...useList];
let result = false;
if(!word || !word.length) {
return true;
}

// 上
if(x > 0 && board[x-1][y] === word[0] && !positionInList([x-1,y], list)) {
const l = [...list]
l.push([x-1, y]);
result = result || searchDFS(board, [x-1,y], shiftWord(word), l);
}

// 下
if (x < board.length-1 && board[x+1][y] === word[0] && !positionInList([x+1,y], list)) {
const l  = [...list]
l.push([x+1, y]);
result = result || searchDFS(board, [x+1,y], shiftWord(word), l);
}

// 左
if (y > 0 && board[x][y-1] === word[0] && !positionInList([x,y-1], list)) {
const l = [...list]
l.push([x, y-1]);
result = result || searchDFS(board, [x,y-1], shiftWord(word), l);
}

// 右
if (y < board[0].length-1 && board[x][y+1] === word[0] && !positionInList([x,y+1], list)) {
const l = [...list]
l.push([x, y+1]);
result = result || searchDFS(board, [x,y+1], shiftWord(word), l);
}

return result;
}

var positionInList = function ([x, y], list = []) {
return list.some(([oX, oY]) => (oX === x && oY === y))
}

var shiftWord = function (word) {
return Array.prototype.slice.call(word, 1).join('')
}


apachecn/AiLearning