【回溯】B009_单词搜索（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.

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.

二、题解

(1) dfs + 回溯

对每一个格子都从头以 $dfs$dfs 策略搜索。

/**
 * @date: 2/5/2020 5:48 PM
 * @Execution info：9ms 击败 36.8% 的j，MB 击败 93.52% 的j
 */
private boolean dfs(char[][] board, int[][] dir, int i, int j, int step, char[] words) {
  if(step == words.length-1) {
    return words[step] == board[i][j];
  }
  if(board[i][j] == words[step]) {
    isVisited[i][j] = true;
    for (int k = 0; k < 4; k++) {
      int nX = i + dir[k][0];
      int nY = j + dir[k][1];
      boolean isValid = nX >= 0 && nX < board.length && nY >= 0 && nY < board[0].length && !isVisited[nX][nY];
      if(isValid && dfs(board, dir, nX, nY, step+1, words)) {
        return true;
      }
    }
    isVisited[i][j] = false;
  }
  return false;
}

复杂度分析

• 时间复杂度： $O()$O()，
• 空间复杂度：$O()$O()，

---

(2) 回溯

/**
 * @date: 2/5/2020 5:30 PM
 * @Execution info：5ms 击败 96.55% 的j，MB 击败 28.94% 的j
 */
private boolean backtrack(char[][] board, String word, int i, int j, int step) {
  if (step == word.length()) {
    return true;
  }
  if (i < 0 || j < 0 || i >= board.length || j >= board[0].length) {
    return false;
  }
  if (board[i][j] == word.charAt(step)) {
    char c = board[i][j];
    board[i][j] = '#';
    if (backtrack(board, word, i+1, j, step + 1)) return true;
    if (backtrack(board, word, i-1, j, step + 1)) return true;
    if (backtrack(board, word, i, j+1, step + 1)) return true;
    if (backtrack(board, word, i, j-1, step + 1)) return true;
    board[i][j] = c;
  }
  return false;
}