Description

Submission

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int nRow = board.size();
        int nCol = board[0].size();
        vector<vector<bool>> taken(nRow, vector<bool>(nCol, false));
        for(int i = 0; i < nRow; ++i) {
            for(int j = 0; j < nCol; ++j) {
                if(backtrack(board, taken, word, 0, i, j)) return true;
            }
        }
        return false;
    }
private:
    bool backtrack(vector<vector<char>>& board, vector<vector<bool>>& taken,
               string& word, int ptr, int i, int j) {
        if(ptr == word.size()) return true;
        if(i < 0 || i == board.size() || j < 0 || j == board[0].size()) return false;
        if(taken[i][j]) return false;
        if(word[ptr] != board[i][j]) return false;
        
        taken[i][j] = true;
        if(backtrack(board, taken, word, ptr + 1, i + 1, j)) return true;
        if(backtrack(board, taken, word, ptr + 1, i - 1, j)) return true;
        if(backtrack(board, taken, word, ptr + 1, i, j + 1)) return true;
        if(backtrack(board, taken, word, ptr + 1, i, j - 1)) return true;
        taken[i][j] = false;
        return false;
    }
};