LeetCode 79. 单词搜索

作者:Choi Yang

更新于:7 个月前

字数统计:986 字

阅读时长:4 分钟

题目描述

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false

提示：

board 和 word 中只包含大写和小写英文字母。
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/word-search 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

上一期做了单词搜索 2 hard 版本之后，这道题也想用字典树玩一玩，没想到超时了，后面一想，数据确实有点大，而且对于一个单词来说，建立一颗字典树岂不是很浪费，还要花时间码代码...

本题也是回溯的思路，不过期间做了一点小优化，还是通过动态更改当前所走的格子，省去了那份 开辟vis 数组的空间。

对于递归层次，由于最后一次计算时，层次多算了一次（即多加了一次），所以条件为 >。

javascript

var exist = function (grid, word) {
  let dfs = (x, y, t) => {
    // 最后一次还会 +1 因此，条件是大于
    if (t > word.length - 1) {
      return true;
    }
    // 剪枝条件
    if (
      x < 0 ||
      x >= grid.length ||
      y < 0 ||
      y >= grid[0].length ||
      grid[x][y] != word[t] ||
      grid[x][y] == "#"
    )
      return false;
    let tmp = grid[x][y];
    // 开始走
    grid[x][y] = "#";
    // 从四个方向搜索，只要一个方向搜索有结果，那么直接返回 true即可
    let res =
      dfs(x + 1, y, t + 1) || dfs(x, y + 1, t + 1) || dfs(x - 1, y, t + 1) || dfs(x, y - 1, t + 1);
    if (res) return true;
    // 回溯（重置）
    grid[x][y] = tmp;
    return false;
  };
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] == word[0]) {
        let res = dfs(i, j, 0);
        if (res) return true;
      }
    }
  }
  return false;
};

cpp

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size(), n = board[0].size();
        vector<vector<bool>> vis(m, vector<bool>(n, false));
        vector<vector<int>> dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        function<bool(int, int, int)> dfs = <CustomLink title="&" href="int x, int y, int t" /> {
            if (t > word.size() - 1) return true;
            if (x < 0 || x >= m || y < 0 || y >= n || vis[x][y] || board[x][y] != word[t]) return false;
            vis[x][y] = true;
            for (auto d : dir) {
                int nx = x + d[0], ny = y + d[1];
                if (dfs(nx, ny, t + 1)) return true;
            }
            vis[x][y] = false;
            return false;
        };
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == word[0]) {
                    if (dfs(i, j, 0)) return true;
                }
            }
        }
        return false;
    }
};

java

class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        boolean[][] vis = new boolean[m][n];
        int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        boolean dfs(int x, int y, int t) {
            if (t > word.length() - 1) return true;
            if (x < 0 || x >= m || y < 0 || y >= n || vis[x][y] || board[x][y] != word.charAt(t)) return false;
            vis[x][y] = true;
            for (int[] d : dir) {
                int nx = x + d[0], ny = y + d[1];
                if (dfs(nx, ny, t + 1)) return true;
            }
            vis[x][y] = false;
            return false;
        };
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == word.charAt(0)) {
                    if (dfs(i, j, 0)) return true;
                }
            }
        }
        return false;
    }
}

python

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        vis = [[False] * n for _ in range(m)]
        dir = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        def dfs(x, y, t):
            if t > len(word) - 1: return True
            if x < 0 or x >= m or y < 0 or y >= n or vis[x][y] or board[x][y] != word[t]: return False
            vis[x][y] = True
            for d in dir:
                nx, ny = x + d[0], y + d[1]
                if dfs(nx, ny, t + 1): return True
            vis[x][y] = False
            return False
        for i in range(m):
            for j in range(n):
                if board[i][j] == word[0]:
                    if dfs(i, j, 0): return True
        return False

学如逆水行舟，不进则退

Contributors

Choi Yang