题目描述
79. Word Search
回溯
代码一，使用used数组
class Solution {vector<pair<int,int>> directions{{0,1},{0,-1},{1,0},{-1,0}};vector<vector<bool>> used;
public:bool exist(vector<vector<char>>& board, string word) {used.resize(board.size(),vector<bool>(board[0].size(),false));for(int i = 0;i < board.size();i++){for(int j = 0;j < board[i].size();j++){if(board[i][j] != word[0] || used[i][j] == true)continue;used[i][j] = true;if(backtrack(board,word,1,i,j))return true;used[i][j] = false;}}return false;}bool backtrack(vector<vector<char>>& board, string &word,int idx,int row,int col){if(idx == word.size())return true;for(const auto& dir: directions){int newrow = row+dir.first;int newcol = col+dir.second;if(newrow<0 || newrow>=board.size() || newcol<0 || newcol>= board[0].size())continue;if(used[newrow][newcol])continue;if(board[newrow][newcol] == word[idx]){used[newrow][newcol] = true;if(backtrack(board,word,idx+1,newrow,newcol))return true;used[newrow][newcol] = false;}}return false;}
};代码二，不使用used数组
class Solution {vector<pair<int,int>> directions{{0,1},{0,-1},{1,0},{-1,0}};
public:bool exist(vector<vector<char>>& board, string word) {for(int i = 0;i < board.size();i++){for(int j = 0;j < board[i].size();j++){if(board[i][j] != word[0])continue;board[i][j] = '#';//word仅由大小写英文字母组成，将board[i][j]标记为#表示board[i][j]已经被使用if(backtrack(board,word,1,i,j))return true;board[i][j] = word[0];//恢复原字符}}return false;}bool backtrack(vector<vector<char>>& board, string &word,int idx,int row,int col){if(idx == word.size())return true;for(const auto& dir: directions){int newrow = row+dir.first;int newcol = col+dir.second;if(newrow<0 || newrow>=board.size() || newcol<0 || newcol>= board[0].size())continue;if(board[newrow][newcol] == word[idx]){board[newrow][newcol] = '#';if(backtrack(board,word,idx+1,newrow,newcol))return true;board[newrow][newcol] = word[idx];//恢复原字符}}return false;}
};
