力扣每日一题 - 【单词搜索】

题目链接

视频链接

class Solution {
public:
    int op1[4] = {0, 1, 0, -1};
    int op2[4] = {1, 0, -1, 0}; 
    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(dfs(board, word, i, j, 0)) return true;  
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>>& board, string word, int x,int y, int u){
        if(board[x][y] != word[u]) return false;   //不匹配 
        if(u == word.size() - 1) return true;   //走到结尾位置，返回true
        char ch = board[x][y]; //提前记录，回溯的时候用于清空标记位
        board[x][y] = '.';     //标记位

        for(int i  = 0; i < 4; i++){
            int a = x + op1[i] , b = y + op2[i];  //枚举四种走向
            if(a >= board.size() || a < 0 || b >= board[0].size() || b < 0
            || board[a][b] == '.' ) continue;   //下一个位置不合法，就跳过
            if(dfs(board, word, a, b, u + 1)) return true;  //来到下一个位置，继续作为起点
        }
        board[x][y] = ch;  //还原现场值
        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