心之所向便是光

Leetcode 79.单词搜索

  • 2021-06-17
  • 作者 Ender
  • 3.67K 字
  • 次阅读

题目描述：

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

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

示例 1：

1
2
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2：

1
2
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

示例 3：

1
2
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

提示：

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board 和 word 仅由大小写英文字母组成

链接：

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

题目分析

  这道题是在一个二维的表格中寻找一个单词，由于每次搜索的格子是相邻的，我们很容易可以想到 DFS（深度优先搜索）的方法。因为题目要求结点不能重复使用，我们使用一个和 board 同样大小的布尔数组 use 来标记结点是否已经被使用。我们从符合 word[0] 的某个单元格开始搜索，每次往某个方向搜索，如果这个方向的邻结点还没有被使用，并且符合我们需要的下一个字母（word[index]），则从这个结点进行下一层的搜索。当我们搜索到 word 的尽头仍然可以找到符合的字母时，则说明这个单词 word 存在于 board 中，直接返回 true，不再进行搜索。如果当前方向搜索不到则进行回溯，将标记为已使用的单元格还原为未使用，继续进行其他方向的搜索。如果经历了所有的搜索都无法找到，则结果为 false。需要注意的是，初始的 use 需要全部标记为未使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    bool dfs(const vector<vector<char>>& board,
             vector<vector<bool>>& use, int x, int y,
             const string word, int index){
        if(index == word.size()) return true;
        
        if(x > 0 && !use[x-1][y] && board[x-1][y] == word[index]){
            use[x-1][y] = true;
            if(dfs(board, use, x-1, y, word, index+1)) return true;
            use[x-1][y] = false;
        }
        if(y > 0 && !use[x][y-1] && board[x][y-1] == word[index]){
            use[x][y-1] = true;
            if(dfs(board, use, x, y-1, word, index+1)) return true;
            use[x][y-1] = false;
        }
        if(x < board.size()-1 && !use[x+1][y] && board[x+1][y] == word[index]){
            use[x+1][y] = true;
            if(dfs(board, use, x+1, y, word, index+1)) return true;
            use[x+1][y] = false;
        }
        if(y < board[0].size()-1 && !use[x][y+1] && board[x][y+1] == word[index]){
            use[x][y+1] = true;
            if(dfs(board, use, x, y+1, word, index+1)) return true;
            use[x][y+1] = false;
        }
        return false;
    }
public:
    bool exist(vector<vector<char>>& board, string word) {
        for(int i = 0; i < board.size(); i++){
            for(int j = 0; j < board[0].size(); j++){
                if(board[i][j] == word[0]){
                    vector<vector<bool>> use(board.size(), vector<bool>(board[0].size(), false));
                    use[i][j] = true;
                    if(dfs(board, use, i, j, word, 1)) return true;
                }
            }
        }
        return false;
    }
};

  时间复杂度：$O(mn\times3^L)$，其中 $m、n、L$ 分别为 board 的行数、列数和 word 的长度，这是一个比较宽松的上界。我们最多对整个 board 的所有单元格作为起点进行搜索，除了起点，每次搜索最多只有三个方向可以搜索（上一个结点的方向已经被使用），最大搜索长度是单词的长度。我们对于已使用的单元格或者是不符合的字母都是不会进行搜索的，有了这些剪枝实际上的时间复杂度会远远小于这个上界。
  空间复杂度：$O(mn)$，其中 $m、n$ 分别为 board 的行数和列数。我们建立了一个 $m\times n$ 的数组用于标记某个单元格是否已经使用。而 DFS 最大的搜索深度为单词的长度或者是搜满 board，也即 $O(\min(L,mn))$。因此总的空间复杂度为 $O(mn)$。

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
, ,
最后编辑：2021-06-17