[Algorithm] LeetCode 79. Word Search (javascript) — DFS 深度優先搜尋

題目:

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

解法:

function wordSearch(board, word) {
  if (word === "") return true;
  
  for (var row = 0; row < board.length; row++) {
    for (var col = 0; col < board[row].length; col++) {
      if (board[row][col] === word[0]) {
        if (dfs(0, row, col)) return true;
      }
    }
  }
  return false;
  function dfs(index, x, y) {
    if (index === word.length) return true;
    if (!board[x] || !board[x][y]) return false;
    if (board[x][y] !== '#' && board[x][y] === word[index]) {
      var ch = board[x][y];
      board[x][y] = '#';
      
      if (dfs(index + 1, x - 1, y)) return true; //up
      if (dfs(index + 1, x + 1, y)) return true; //down
      if (dfs(index + 1, x, y - 1)) return true; //left
      if (dfs(index + 1, x, y + 1)) return true; //right
      board[x][y] = ch; // backtracking
    }
    return false;
  }
};

原理：

利用Depth-first Search(DFS，深度優先搜尋法)，DFS屬於盲目搜索(uninformed search)，是用來遍尋圖形的演算法。

首先，先找到word第一個字符在board上出現的位置，再從這個位置開始往上、下、左、右尋找，如果都沒有找到對應的字，則回溯(backtracking)到前一個節點，一直重複dfs，直到index等於word長度時，表示找到對應的字符了。另外，需注意邊界條件，確保在board內。

由於遍歷整個m * n 的board，時間複雜度為m * n。而每個點都會往上下左右來尋找， k為word長度，大概要遍歷4^k次，所以總的時間複雜度爲O(mn4^k)

參考:

• 深度優先搜尋法
• [LeetCode][JavaScript]Word Search by Liok