class Solution {
public:
bool flag = false;
bool exist(vector>& board, string word) {
int rows = board.size(), columns = board[0].size();
if(rows * columns < word.length())
return false;
for(int i = 0; i < rows; i++){
for(int j = 0; j < columns; j++){
if(board[i][j] == word[0]){
board[i][j] = '1'; //遍历过的置1
backtrack(board, word, i, j, 1);
board[i][j] = word[0];
}
if(flag)
return true;
}
}
return flag;
}
void backtrack(vector>& board, string& word, int row, int column, int level){
if(level == word.length()){
flag = true;
return;
}
if(flag)
return;
if(row >= 1 && board[row - 1][column] != '1' && board[row - 1][column] == word[level]){ //向上搜索
board[row - 1][column] = '1';
backtrack(board, word, row - 1, column, level + 1);
board[row - 1][column] = word[level];
if(flag)
return;
}
if(row + 1 <= board.size() - 1 && board[row + 1][column] != '1' && board[row + 1][column] == word[level]){ //向下搜索，不能写成row <= board.size() - 2
board[row + 1][column] = '1'; //因为size()是无整形变量，不能为负数
backtrack(board, word, row + 1, column, level + 1); //board.size() - 2 < 0 存在，会导致结果出错
board[row + 1][column] = word[level];
if(flag)
return;
}
if(column >= 1 && board[row][column - 1] != '1' && board[row][column - 1] == word[level]){ //向左搜索
board[row][column - 1] = '1';
backtrack(board, word, row, column - 1, level + 1);
board[row][column - 1] = word[level];
if(flag)
return;
}
if(column + 1 <= board[0].size() - 1 && board[row][column + 1] != '1' && board[row][column + 1] == word[level]){ //向右搜索
board[row][column + 1] = '1';
backtrack(board, word, row, column + 1, level + 1);
board[row][column + 1] = word[level];
if(flag)
return;
}
}
};
Accepted
82/82 cases passed (184 ms)
Your runtime beats 89.91 % of cpp submissions
Your memory usage beats 42.13 % of cpp submissions (7.8 MB)
