LeetCode79 单词搜索

发表于 | 分类于 |
字数统计: 446 | 阅读时长 ≈ 2

链接： https://leetcode-cn.com/problems/word-search/description/

题意

给定一个字母矩阵，所有的字母都与上下左右四个方向上的字母相连。给定一个字符串，求字符串能不能在字母矩阵中寻找到。

解法

又是一道比较明显的要用到回溯的题目，题目本身不难
这里还是练习一种新的回溯的写法
将visit置位放在递归和回溯的前后
用一个引用变量flag来标记是否找到结果
要注意访问visit数组时的细节，下标是乘以列数，之前就在这个位置翻了车 查了很久才找出来
用一个map数组来提前确定矩阵中是否存在单词中需要的字母

代码

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
43
44
45
46
47
class Solution {
public:
    void dfs(int pos, string word, int x, int y, vector<vector<char>>& board, vector<int>& visit, bool& find) {
        int m = board.size(), n = board[0].size();
        if (x < 0 || x >= m || y < 0 || y >= n) {
            return;
        }
        if (visit[x * n + y] || find || board[x][y] != word[pos]) {
            return;
        }
        if (pos == word.size() - 1) {
            find = true;
            return;
        }
        int dx[4] = {1, 0, -1, 0};
        int dy[4] = {0, 1, 0, -1};
        visit[x * n + y] = 1;
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i], yy = y + dy[i];
            dfs(pos + 1, word, xx, yy, board, visit, find);
        }
        visit[x * n + y] = 0;
    }

    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size(), n = board[0].size();
        map<char, int> chars;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                chars[board[i][j]] = 1;
            }
        }
        for (char ch: word) {
            if (chars[ch] == 0) {
                return false;
            }
        }
        vector<int> visit(m * n);
        bool find = false;
        for(int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(0, word, i, j, board, visit, find);
            }
        }
        return find;
    }
};