LeetCode79. 单词搜索

更新: 1/31/2026 字数: 0 字 时长: 0 分钟

题目链接：LeetCode79. 单词搜索

题目大意就是找到连续的（上下左右）单词，不允许重复使用。

我们看到数据也不大，很明显就是dfs+回溯的方法，先遍历每一个点如果与单词第一个字符匹配则开始搜索，搜索到结果就ans = true，注意回溯即可。

$Solution$:

class Solution {
public:
    int step[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
    int m = 0,n = 0;
    int mark[10][10];
    bool ans = false;
    void dfs(vector<vector<char>>& board, string word, int x, int y,int cur) {
        if(cur == word.length() - 1) {
            ans = true;
            return;
        }
        for(int i = 0;i < 4;i++) {
            int xx = x + step[i][0],yy = y + step[i][1];
            if(xx >= 0 && xx < m && yy >= 0 && yy < n && !mark[xx][yy]) {
                if(board[xx][yy] == word[cur + 1]) {
                    mark[xx][yy] = 1;
                    dfs(board, word, xx, yy, cur + 1);
                    mark[xx][yy] = 0;
                }
            }
        }
    }
    bool exist(vector<vector<char>>& board, string word) {
        m = board.size(),n = board[0].size();
        for(int i = 0;i < m;i++) {
            for(int j = 0;j < n;j++) {
                if(board[i][j] == word[0]) {
                    mark[i][j] = 1;
                    dfs(board, word, i, j, 0);
                    mark[i][j] = 0;
                }
            }
        }
        return ans;
    }
};