【LeetCode】79. 单词搜索

题目描述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
输出：true

示例 2：

输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “SEE”
输出：true

示例 3：

输入：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 仅由大小写英文字母组成

方法一：回溯法

class Solution {
public:
    bool check(vector<vector<char>>& board, vector<vector<bool>>& flag, int i, int j, string& word, int k){
        if(board[i][j] != word[k]) // 不匹配
            return false;
        else if(k == word.length()-1) // word完成匹配
            return true;
       
        // 定义方向数组，遍历四个方向
        vector<pair<int, int>> directions{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        bool res = false; 
        flag[i][j] = true; // 该位置已被访问
        for(const auto& dir: directions){ // 只读访问
            int new_i = i + dir.first, new_j = j + dir.second; // 下一个要访问的坐标
            // 边界判断
            if(new_i>=0 && new_i<board.size() && new_j>=0 && new_j<board[0].size()){
                if(!flag[new_i][new_j]){ // 未被访问
                    if(check(board, flag, new_i, new_j, word, k+1)){ // 访问下一个位置
                        res = true;        
                        break;
                    }
                }
            }
        }
        flag[i][j] = false;
        return res;
    }
    bool exist(vector<vector<char>>& board, string word) {
        int height = board.size(), width = board[0].size();
        // 是否被使用过，true表示用过，false表示没有
        vector<vector<bool>> flag(height, vector<bool>(width, false)); 

        for(int i=0; i<height; i++){
            for(int j=0; j<width; j++){
                if(check(board, flag, i, j, word, 0)){
                    return true;
                }
            }
        }
    return false;
    }
};
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

心得

• 这道题和本科时候做的走迷宫很像，但是我一开始的方法如果遇到这种情况就会出错：[‘CAA’, ‘AAA’, ‘BCD’]，查找’AAB’，我选择右下左上的方法遍历，对于board[1][1]的’A’，我先遍历了右边，即board[1][2]的’A’，再向下遍历board[2][2]的’D’，不匹配导致该循环结束，进而开始遍历board[1][2]。其实board[1][1] -> board[1][0] -> board[2][0]是正确答案，但是我的代码没办法走到这条线路。
• 看了题解，用到了回溯方法。

设函数 check(i,j,k) 表示判断以网格的 (i,j)位置出发，能否搜索到单词 word[k…]，其中word[k…] 表示字符串word从第 k个字符开始的后缀子串。如果能搜索到，则返回 true，反之返回false。函数 check(i,j,k) 的执行步骤如下：

• 如果 board[i][j]≠s[k]，当前字符不匹配，直接返回false。
• 如果当前已经访问到字符串的末尾，且对应字符依然匹配，此时直接返回true。
• 否则，遍历当前位置的所有相邻位置。如果从某个相邻位置出发，能够搜索到子串 word[k+1…]，则返回 true，否则返回 false。
  这样，我们对每一个位置 (i,j)都调用函数 check进行检查：只要有一处返回 true，就说明网格中能够找到相应的单词，否则说明不能找到。
  为了防止重复遍历相同的位置，需要额外维护一个与 board等大的flag数组，用于标识每个位置是否被访问过。每次遍历相邻位置时，需要跳过已经被访问的位置。