Eric's Blogs

Better Code, Better Life

0%

矩阵中的路径

发表于 分类于
本文字数： 3.7k 阅读时长 ≈ 3 分钟

题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如

1
2
3
a b c e
s f c s
a d e e

矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

解答

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
char[] mat, str;
int X, Y;

class P {
    int x, y;
    char c;

    public P(int x, int y) {
        this.x = x;
        this.y = y;
        if (x < 0 || y < 0 || x >= X || y >= Y) {
            c = ' ';
        } else {
            this.c = mat[Y * x + y];
        }
    }

    @Override
    public boolean equals(Object obj) {
        return x == ((P) obj).x && y == ((P) obj).y;
    }

    @Override
    public int hashCode() {
        int i = Integer.valueOf(x + "" + y);
        return i;
    }
}

public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
    mat = matrix;
    this.str = str;
    X = rows;
    Y = cols;
    List<P> list = findFirst(str[0]);
    for (P p : list) {
        if (findPath(p)) {
            return true;
        }
    }
    return false;
}

Set<P> set = new HashSet<>();
boolean ok = false;

private boolean findPath(P p) {
    ok = false;
    set.clear();
    dfs(p, 0);
    if (ok) {
        return true;
    } else {
        return false;
    }
}

private void dfs(P p, int i) {

    if (ok || p.c == ' ' || set.contains(p)) {
        return;
    }
    if (p.c == str[i]) {
        if (i == str.length - 1) {/** 路径找到了 */
            ok = true;
            return;
        }
        set.add(p);
        dfs(new P(p.x + 1, p.y), i + 1);
        dfs(new P(p.x - 1, p.y), i + 1);
        dfs(new P(p.x, p.y + 1), i + 1);
        dfs(new P(p.x, p.y - 1), i + 1);
    }
}

private List<P> findFirst(char c) {
    List<P> list = new ArrayList<>();
    for (int i = 0; i < X; i++) {
        for (int j = 0; j < Y; j++) {
            P p = new P(i, j);
            if (p.c == c) {
                list.add(p);
            }
        }
    }
    return list;
}

官方题解

链接：https://www.nowcoder.com/questionTerminal/c61c6999eecb4b8f88a98f66b273a3cc?answerType=1&f=discussion
来源：牛客网

方法：DFS

这道题大家都知道是DFS的题，关键是怎么可以快速并且正确的写出，是本题解讨论的重点。
首先解释一下递归函数。
递归函数：就是当前处理的问题是什么，并且下一次在规模减小的情况下处理相同的问题。
比如此题：当前处理的问题是：判断字符串str[0 … len]是否在mat中匹配，显然下一次递归处理的问题是:如果str[0]已经匹配，则判断字符串str[1 … len]是否在mat中匹配。

这里先给出一个我认为比较清晰的DFS模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
dfs(){

    // 第一步，检查下标是否满足条件

    // 第二步：检查是否被访问过，或者是否满足当前匹配条件

    // 第三步：检查是否满足返回结果条件

    // 第四步：都没有返回，说明应该进行下一步递归
    // 标记
    dfs(下一次)
    // 回溯
}  


main() {
    for (对所有可能情况) {
        dfs()
    }
}

上面每步的顺序都不能颠倒。

所以，对于这道题来说，首先dfs()的参数是什么，返回值是什么。
可以像这样：

1
2
3
// i, j 表示mat中的位置， pos表示当前正在匹配的字符串str的下标
// 成功返回整个字符串str, 则返回true, 否则返回false
bool dfs(int i, int j, int pos, char *str);

主函数该怎么写？可以像如下这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 几个全局变量，便于程序的简洁，只是在刷题中建议
char *mat = 0;
int h = 0, w = 0;
int str_len = 0;
int dir[5] = {-1, 0, 1, 0, -1};
bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        mat = matrix;
        h = rows, w = cols;
         str_len = strlen(str);

        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (dfs(i, j, 0, str)) {
                    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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public:
    char *mat = 0;
    int h = 0, w = 0;
    int str_len = 0;
    int dir[5] = {-1, 0, 1, 0, -1};

    bool dfs(int i, int j, int pos, char *str) {
        // 因为dfs调用前，没有进行边界检查，
        // 所以需要第一步进行边界检查，
        // 因为后面需要访问mat中元素，不能越界访问
        if (i < 0 || i >= h || j < 0 || j >= w) {
            return false;
        }

        char ch = mat[i * w + j];
        // 判断是否访问过
        // 如果没有访问过，判断是否和字符串str[pos]匹配
        if (ch == '#' || ch != str[pos]) {
            return false;
        }

         // 如果匹配，判断是否匹配到最后一个字符
        if (pos + 1  == str_len) {
            return true;
        }

        // 说明当前字符成功匹配，标记一下，下次不能再次进入
        mat[i * w + j] = '#';
        for (int k = 0; k < 4; ++k) {
            if (dfs(i + dir[k], j + dir[k + 1], pos + 1, str)) {
                return true;
            }
        } 
        // 如果4个方向都无法匹配 str[pos + 1]
        // 则回溯， 将'#' 还原成 ch          
        mat[i * w + j] = ch;
        // 说明此次匹配是不成功的
        return false;   
    }
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        mat = matrix;
        h = rows, w = cols;
         str_len = strlen(str);

        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (dfs(i, j, 0, str)) {
                    return true;
                }
            }
        }
        return false;
    }
};

时间复杂度：O(3^k)， 每个位置除当前自己的方向，还有3个方向可以展开。k为str的长度
空间复杂度：O(k), 最大递归栈的深度为k