[Lc]79单词搜索

题目

题解

这道题用递归，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 exist(vector<vector<char>>& board, string word) {
        if(board.empty()||board[0].empty()) return false;
        //判断数组是否为空，为空直接返回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;
    }
    bool DFS(vector<vector<char>>& board,string word,int idx,int i,int j){
        if(idx==word.size()) return true;//若搜寻已经超过单词长度，返回true
        if(i<0||j<0||i>=board.size()||j>=board[0].size()||board[i][j]!=word[idx]) return false;//若搜寻超过数组边界，或者搜寻处的值不等于当前搜寻的字母，返回false
        char tmp = board[i][j];//暂存当前字母
        board[i][j] = '0';//若已经搜索过数组该处，将其改为'0'
        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);//用递归对四个方向进行搜寻，搜寻word中下一位
        board[i][j] = tmp;//到这一步说明上述四个方向都未搜到字母，则进行回溯，并将该处的值变为原来的值，即不标记为搜寻过
        return res;
    }
};