单词搜索 #34
Description
习题
出处：LeetCode 算法第79题
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] 给定 word = "ABCCED", 返回 true. 给定 word = "SEE", 返回 true. 给定 word = "ABCB", 返回 false.
思路
采用深度遍历搜索的方式，遍历所有可能性，得到结果
解答
var exist = function (board, word) {
var row = board.length;
var col = board[0].length;
var visit = [];
for (var x = 0; x < row; x++) {
visit[x] = [];
}
for (var i = 0; i < row; i++) {
for (var j = 0; j < col; j++) {
if (dfs(board, visit, i, j, 0, word)) {
return true;
}
}
}
return false;
};
function dfs(board, visit, row, col, index, word) {
if (index == word.length) {
return true;
}
if (row < 0 || col < 0 || row >= board.length || col >= board[0].length) {
return false;
}
var ch = word[index];
if (!visit[row][col] && ch == board[row][col]) {
visit[row][col] = true;
var res = dfs(board, visit, row - 1, col, index + 1, word) || dfs(board, visit, row + 1, col, index + 1, word) || dfs(board, visit, row, col - 1, index + 1, word) || dfs(board, visit, row, col + 1, index + 1, word);
visit[row][col] = false;
return res;
}
return false;
}