Leetcode: 【每日一题】- 2019-08-07 - 79. 单词搜索

Created on 6 Aug 2019 · 4Comments · Source: azl397985856/leetcode

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Daily Question

Source

azl397985856

All 4 comments

``` .js
/**

@param {character[][]} board
@param {string} word
@return {boolean}
*/
var exist = function (board, word) {
var visited = Array.from({
length: board.length
}, () => new Array(board.length).fill(false));

for (var i = 0; i < board.length; i++) {
    for (var j = 0; j < board[i].length; j++) {
        if (board[i][j] == word[0]) {
            if (temp(i, j, 0)) {
                return true;
            }
        }
    }
}
return false;

function temp(x, y, index) {
    if (x < 0 || y < 0 || x >= board.length || y >= board[0].length) return false;
    if (visited[x][y]) return false;
    if (index == word.length - 1 && board[x][y] == word[index]) return true;
    if (board[x][y] != word[index]) return false;

    visited[x][y] = true;
    var rel = temp(x - 1, y, index + 1) || temp(x + 1, y, index + 1) || temp(x, y - 1, index + 1) || temp(x, y + 1, index + 1);
    if (rel) return true;
    visited[x][y] = false;
    return false;
}

};
```