79. Word Search.md

79. Word Search

思路

思路一

这道题是典型的DFS，原二维数组就像是一个迷宫，可以上下左右四个方向行走，我们以二维数组中每一个数都作为起点和给定字符串做匹配， 我们还需要一个和原数组等大小的visited数组来记录是否已经被访问过。如果board的当前字符和目标字符串word对应的字符相等，则对其上下左右四个邻字符分别调用DFS的递归函数，只要有一个返回true， 那么就表示可以找到对应的字符串，否则就不能找到。

注意：如代码所示，在每次从头调用DFS时不需要对visited进行初始化，因为上一次DFS返回false前已经把visited[i][j]改成了false。

思路二

其实和思路一差不多，也是DFS，但是不使用visited数组，我们用原数组board来记录某个元素是否被访问过，若被访问过就将board对应位置改成字符*，代码与思路一几乎一样。

C++

思路一

class Solution {
private:
    bool DFS(vector<vector<bool>>&visited, int i, int j, vector<vector<char>>& board, string &word, int len){
        if(visited[i][j] || board[i][j] != word[len]) return false;
        if(len + 1 == word.size()) return true;
        visited[i][j] = true;
        if(i > 0 && DFS(visited, i - 1, j, board, word, len + 1)) return true;
        if(j > 0 && DFS(visited, i, j - 1, board, word, len + 1)) return true;
        if(1 + i < board.size() && DFS(visited, i + 1, j, board, word, len + 1)) return true;
        if(1 + j < board[0].size() && DFS(visited, i, j + 1, board, word, len + 1)) return true;
        visited[i][j] = false; // 恢复visited
        return false;
    }
public:
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size(), n = board[0].size();
        vector<vector<bool>> visited(m ,vector<bool>(n, false));
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                // 这里不需要对visited进行初始化，因为此时的visited必定全false
                if(DFS(visited, i, j, board, word, 0)) return true;
            }
        }
        return false;
        
    }
};

思路二

class Solution {
private:
    bool DFS(int i, int j, vector<vector<char>>& board, string &word, int len){
        // if(board[i][j] != '*' || board[i][j] != word[len]) return false;
        if(board[i][j] != word[len]) return false; // 等价于上句
        if(len + 1 == word.size()) return true;
        
        char bk = board[i][j];
        board[i][j] = '*';
        if(i > 0 && DFS(i - 1, j, board, word, len + 1)) return true;
        if(j > 0 && DFS(i, j - 1, board, word, len + 1)) return true;
        if(1 + i < board.size() && DFS(i + 1, j, board, word, len + 1)) return true;
        if(1 + j < board[0].size() && DFS(i, j + 1, board, word, len + 1)) return true;
        board[i][j] = bk;
        return false;
    }
public:
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size(), n = board[0].size();
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(DFS(i, j, board, word, 0)) return true;
            }
        }
        return false;
    }
};