没有输出的输入是不完整的

0%

剑指offer-矩阵中的路径

发表于 更新于 分类于
本文字数： 1.6k 阅读时长 ≈ 2 分钟

本文为剑指 offer 系列第六十二篇。
主要知识点为数组，在矩阵中查找对应的字符串序列，类似于走迷宫或者找包围区间的题目。

题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

解题思路

依次把矩阵中的每个结点作为起点，向四周寻找字符串的下一个字符。一条路走不通就返回尝试其他方向，匹配到字符串的结束标志’\0’时返回true；所有起点和路径都试过后仍未找到，才返回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
class Solution {
public:
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        if(rows<=0 || cols<=0 || !str || !matrix) return false;
        vector<bool> flags(rows*cols,0);
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                if(helper(matrix,rows,cols,i,j,str,flags)) return true;
            }
        }
        return false;
    }
    
    bool helper(char* matrix,int rows,int cols,int i,int j,char* str,vector<bool> flags){
        if(*str == '\0') return true;
        if(i >= 0 && j >= 0 && i < rows && j < cols && matrix[i*cols+j] == *str && flags[i*cols+j] == false){
            flags[i*cols+j] = true;
            bool find = false;
            find = helper(matrix,rows,cols,i,j+1,str+1,flags)
                ||helper(matrix,rows,cols,i,j-1,str+1,flags)
                ||helper(matrix,rows,cols,i+1,j,str+1,flags)
                ||helper(matrix,rows,cols,i-1,j,str+1,flags);
            if(find == false){
                flags[i*cols+j] = false;
            }
            return find;
        }
        return false;
    }


};

记N=rowscols，L为字符串长度与N中的较小值。回溯会尝试不同路径，时间可能随L指数增长；这里每层还按值复制flags，宽松的时间上界为O(N^2 * 4^L)，峰值辅助空间为O(N(L+1))。
以上，本题结束！