LeetCode 面试题12 - 矩阵中的路径

发表于 更新于 分类于 阅读次数：

题目链接：LeetCode 面试题12 - 矩阵中的路径

DFS匹配，注意找到答案就跳出，渐进时间复杂度 $ O(nm|s|^2) $。

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
48
49
50
51
52
53
class Solution {
public:
    int n, m;
    vector <vector <char>> a;
    vector <vector <bool>> vis;
    string s;
    bool status;

    static constexpr int dx[4] = {-1, 0, 1, 0};
    static constexpr int dy[4] = {0, 1, 0, -1};

    void dfs(int x, int y, int p) {
        if (status == true) return;
        if (p == s.size() - 1 && a[x][y] == s[p]) {
            status = true;
            return;
        }
        if (a[x][y] != s[p]) {
            return;
        }
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (!(nx >= 0 && nx <= n - 1 && ny >= 0 && ny <= m - 1) || vis[nx][ny]) { 
                continue;
            }
            vis[nx][ny] = 1;
            dfs(nx, ny, p + 1);
            vis[nx][ny] = 0;
        }
    }

    bool exist(vector<vector<char>>& board, string word) {
        n = board.size();
        m = board.at(0).size();
        a = board;
        s = word;
        vis.resize(n);
        for (auto &v: vis) v.resize(m);
        status = false;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                vis[i][j] = 1;
                dfs(i, j, 0);
                vis[i][j] = 0;
                if (status == true) {
                    return true;
                }
            }
        }
        return false;
    }
};