环球要闻：矩阵中的路径

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

环球要闻：矩阵中的路径

2023-02-15 11:12:17 来源：博客园

(相关资料图)

问题：矩阵中的路径剑指 Offer 12. 矩阵中的路径 - 力扣（LeetCode）

思路：DFS+剪枝；

首先可以从矩阵中的任何一点出发进行搜索；时间复杂度O(MN)；

从某个board[ i ][ j ]出发，判断它的四个方向；下、上、右、左，走过的点标记为 " \0 " ，用来防止重复访问；因此至多只有三个方向可以走，但是通写成四个dfs，用 || 连接；

board[ i ][ j ] == word[ k] 就继续寻找下一个点；

直到 k == word.size() -1;完全匹配时进行回溯，并将标记的点还原为原来的值；

时间复杂度：O(MN 3^k); 空间复杂度：O(K).

class Solution {public:    bool exist(vector>& board, string word) {        row = board.size();        col = board[0].size();        for(int i = 0; i < row; ++i){            for(int j = 0; j< col;++j){                if(dfs(board,word,i,j,0)) return true;//从一个点开始dfs；匹配失败就进行下一次dfs            }        }        return false;    }private:    int row,col;    bool dfs(vector>& b, string w, int x,int y,int k){        if(y >= col || y <0 || x < 0 || x >= row || b[x][y] != w[k]) return false;        if(k == w.size() -1) return true;        b[x][y] = "\0";        bool res = dfs(b,w,x+1,y,k+1)||dfs(b,w,x-1,y,k+1)||                    dfs(b,w,x,y+1,k+1)||dfs(b,w,x,y-1,k+1);        b[x][y] = w[k];        return res;    }};

关键词：时间复杂度空间复杂度