leecode/problems/79.word-search.md
2020-05-22 18:17:19 +08:00

8.1 KiB
Raw Permalink Blame History

题目地址

https://leetcode.com/problems/word-search/

题目描述

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.

思路

在2D表中搜索是否有满足给定单词的字符组合要求所有字符都是相邻的方向不限). 题中也没有要求字符的起始和结束位置。

在起始位置不确定的情况下扫描二维数组找到字符跟给定单词的第一个字符相同的四个方向分别DFS搜索 如果任意方向满足条件,则返回结果。不满足,回溯,重新搜索。

举例说明:如图二维数组,单词:"SEE"

1. 扫描二维数组找到board[1,0] = word[0],匹配单词首字母。
2. 做DFS右 四个方向)

如下图:

word search 1

起始位置10判断相邻的字符是否匹配单词下一个字符 E.

1. 标记当前字符10为已经访问过board[1][0] = '*'
2. 上00字符为 'A' 不匹配, 
3. 下20字符为 'A',不匹配,
4. 左(-10超越边界不匹配,
5. 右11字符 'F',不匹配

如下图:

word search 2

由于从起始位置DFS都不满足条件所以

1. 回溯标记起始位置10为未访问。board[1][0] = 'S'. 
2. 然后继续扫描二维数组找到下一个起始位置13

如下图:

word search 3

起始位置13判断相邻的字符是否匹配单词下一个字符 E.

1. 标记当前字符1, 3为已经访问过board[1][3] = '*'
2. 上03字符为 'E', 匹配, 继续DFS搜索参考位置为03位置DFS搜索步骤描述
3. 下23字符为 'E',匹配, #2匹配先进行#2 DFS搜索由于#2 DFS搜索没有找到与单词匹配继续DFS搜索参考位置为23DFS搜索步骤描述
4. 左12字符为 'C',不匹配,
5. 右14超越边界不匹配

如下图:

word search 4

位置03满足条件继续DFS判断相邻的字符是否匹配单词下一个字符 E

1. 标记当前字符03为已经访问过board[0][3] = '*'
2. 上 -13超越边界不匹配
3. 下13已经访问过
4. 左02字符为 'C',不匹配
5. 右14超越边界不匹配

如下图

word search 5

从位置03DFS不满足条件继续位置23DFS搜索

1. 回溯标记起始位置03为未访问。board[0][3] = 'E'. 
2. 回到满足条件的位置23继续DFS搜索判断相邻的字符是否匹配单词下一个字符 'E'
3. 上 (13已访问过
4. 下33超越边界不匹配
5. 左22字符为 'E',匹配
6. 右24超越边界不匹配

如下图:

word search 6

单词匹配完成,满足条件,返回 True. word search 7

复杂度分析

  • 时间复杂度: O(m*n) - m 是二维数组行数, n 是二维数组列数
  • 空间复杂度: O(1) - 这里在原数组中标记当前访问过,没有用到额外空间

注意:如果用 Set 或者是 boolean[][]来标记字符位置是否已经访问过,需要额外的空间 O(m*n).

关键点分析

  • 遍历二维数组的每一个点找到起始点相同的字符做DFS
  • DFS过程中要记录已经访问过的节点防止重复遍历这里Java Code中* 表示当前已经访问过也可以用Set或者是boolean[][]数组记录访问过的节点位置。
  • 是否匹配当前单词中的字符,不符合回溯,这里记得把当前 * 重新设为当前字符。如果用Set或者是boolean[][]数组,记得把当前位置重设为没有访问过。

代码 (Java/Javascript/Python3)

Java Code

public class LC79WordSearch {
  public boolean exist(char[][] board, String word) {
    if (board == null || board.length == 0 || board[0].length == 0
        || word == null || word.length() == 0) return true;
    int rows = board.length;
    int cols = board[0].length;
    for (int r = 0; r < rows; r++) {
      for (int c = 0; c < cols; c++) {
        // scan board, start with word first character 
        if (board[r][c] == word.charAt(0)) {
          if (helper(board, word, r, c, 0)) {
            return true;
          }
        }
      }
    }
    return false;
  }
  
  private boolean helper(char[][] board, String word, int r, int c, int start) {
    // already match word all characters, return true
    if (start == word.length()) return true;
    if (!isValid(board, r, c) ||
        board[r][c] != word.charAt(start)) return false;
    // mark visited
    board[r][c] = '*';
    boolean res = helper(board, word, r - 1, c, start + 1) // 上
        ||  helper(board, word, r + 1, c, start + 1)       // 下
        ||  helper(board, word, r, c - 1, start + 1)       // 左
        ||  helper(board, word, r, c + 1, start + 1);      // 右
    // backtracking to start position
    board[r][c] = word.charAt(start);
    return res;
  }
  
  private boolean isValid(char[][] board, int r, int c) {
    return r >= 0 && r < board.length && c >= 0 && c < board[0].length;
  }
}

Python3 Code

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m = len(board)
        n = len(board[0])
        
        def dfs(board, r, c, word, index):
            if index == len(word):
                return True
            if r < 0 or r >= m or c < 0 or c >= n or board[r][c] != word[index]:
                return False
            board[r][c] = '*'
            res = dfs(board, r - 1, c, word, index + 1) or dfs(board, r + 1, c, word, index + 1) or dfs(board, r, c - 1, word, index + 1) or dfs(board, r, c + 1, word, index + 1)
            board[r][c] = word[index]
            return res
        
        for r in range(m):
            for c in range(n):
                if board[r][c] == word[0]:
                    if dfs(board, r, c, word, 0):
                        return True

Javascript Code from @lucifer

/*
 * @lc app=leetcode id=79 lang=javascript
 *
 * [79] Word Search
 */
function DFS(board, row, col, rows, cols, word, cur) {
  // 边界检查
  if (row >= rows || row < 0) return false;
  if (col >= cols || col < 0) return false;

  const item = board[row][col];

  if (item !== word[cur]) return false;

  if (cur + 1 === word.length) return true;

  // 如果你用hashmap记录访问的字母 那么你需要每次backtrack的时候手动清除hashmap并且需要额外的空间
  // 这里我们使用一个little trick
  
  board[row][col] = null;

  // 上下左右
  const res =
    DFS(board, row + 1, col, rows, cols, word, cur + 1) ||
    DFS(board, row - 1, col, rows, cols, word, cur + 1) ||
    DFS(board, row, col - 1, rows, cols, word, cur + 1) ||
    DFS(board, row, col + 1, rows, cols, word, cur + 1);

  board[row][col] = item;

  return res;
}
/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
  if (word.length === 0) return true;
  if (board.length === 0) return false;

  const rows = board.length;
  const cols = board[0].length;

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      const hit = DFS(board, i, j, rows, cols, word, 0);
      if (hit) return true;
    }
  }
  return false;
};

参考References

  1. 回溯法 Wiki