[Lc]面试题12矩阵中的路径

题目

注意：本题与主站 79 题相同：(https://leetcode-cn.com/problems/word-search/)

题解

这道题用递归，DFS，找到和首字母相同的就继续找下去，找到不同的就回溯再找首字母

• 时间复杂度：${\mathcal{O}}((M\times N)^2)$。
• 空间复杂度：${\mathcal{O}}(M\times N)$。
  分析见(https://leetcode-cn.com/problems/word-search/solution/tu-jie-di-gui-shen-du-you-xian-sou-suo-by-z1m/)

class Solution {
public:
    bool DFS(vector<vector<char>>& board, string word, int idx, int i, int j){//dfs参数包括word的下标，数组的下标
        if(idx==word.size()) return true;//若word全部找到，返回true
        //若超出数组或者字符不等，返回false
        if(i<0 || j<0 || i>=board.size() || j>=board[0].size() || board[i][j]!=word[idx]) return false;
        char tmp = board[i][j];
        board[i][j] = '#';//遍历过的字符标记一下，防止二次遍历
        bool res = DFS(board,word,idx+1,i-1,j) ||
                   DFS(board,word,idx+1,i,j-1) ||
                   DFS(board,word,idx+1,i+1,j) ||
                   DFS(board,word,idx+1,i,j+1);
        board[i][j] = tmp;//回溯就把字符复原
        return res;

    }
    bool exist(vector<vector<char>>& board, string word) {
        if(board.empty() || board[0].empty()) return false;
        for(int i=0; i<board.size(); ++i){
            for(int j=0; j<board[0].size(); ++j){
                if(DFS(board,word,0,i,j)) return true;
            }
        }
        return false;
    }
};