单词搜索

[louzhedong]

习题

出处：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;
}