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;
}
};