79_WordSearch - a920604a/leetcode GitHub Wiki

class Solution {
public:
    bool backtracking(vector<vector<char>>& board, string word, int i, int j,int k,  vector<vector<bool>> & visited){
        if(word.size() == k) return true;
        int n = board.size() , m= board[0].size();
        if(i<0 || j< 0 || i>n-1 || j>m-1 || visited[i][j]) return false;
        
        if(board[i][j] !=word[k]) return false;
        visited[i][j] = true;
        bool ret =  backtracking(board, word, i+1,j, k+1, visited) || \
            backtracking(board, word, i,j+1, k+1, visited) || \
            backtracking(board, word, i-1,j, k+1, visited) || \
            backtracking(board, word, i,j-1, k+1, visited) ;
        
        visited[i][j] = false;
        return ret;
        
    }
    bool exist(vector<vector<char>>& board, string word) {
        int n = board.size() , m= board[0].size();
        vector<vector<bool>> visited(n,vector<bool>(m, false));
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){   
                if(board[i][j] == word[0] &&  backtracking(board, word, i, j, 0, visited)) return true;
            }
        }
        
        return false;
    }
};