Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent"
cells are those horizontally or vertically neighboring. The same letter cell may not be used
more than once.
cells are those horizontally or vertically neighboring. The same letter cell may not be used
more than once.
For example, Given board =
[
["ABCE"],
["SFCS"],
["ADEE"]
]
word = "ABCCED", -> returns true,word =
"SEE", -> returns true,word =
"ABCB", -> returns false.
Hide Tags
Show Similar Problems
Analysis:
This is a Backtracking problem.
The critical part is how to design the backtracking for this case. The searching for the first capital in word should not be in the backtracking procedure, otherwise, it's difficult to implement it. We start to use backtracking from the second searching.
The trivial thing here is the four possible candidates for each searching, namely the upper one, right one, lower one and the left one.
Also, the boundary should be taken into consideration.
In the same time, we need to maintain a flag for each character in the board to hold the information that whether it has been used or not. If the character has been used it can not be used again. Furthermore, if a branch of searching fails, we need to set the flag back for future use.
It needs a lot of patience to correctly finish this problem.
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//codes 32ms
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
if (board.size() == 0)return 0;
//allocate
a dynamic array (one dimention)
int *flag = new int[board.size()*board[0].size()];
memset(flag, 0, board.size()*board[0].size()*sizeof(int));//fill the memory,
0-not used; 1-used;
//find
the first match
for (int i = 0; i < board.size(); i++){
for (int j = 0; j < board[0].size(); j++){
if (board[i][j] == word[0]){
flag[i*board[0].size()+j] = 1;
if (word.size() == 1)return true;
if (judge(board, i, j, word, 1, flag))return true;
else flag[i*board[0].size() + j] = 0;
}
}
}
//delete
new array
delete[]flag;
return false;
}
//checking
the four adjacent neighbors
bool judge(vector<vector<char>>& board, int i, int j, string word, int n, int*flag){
//check board[i-1,j]
if (i - 1 >= 0 && board[i - 1][j] == word[n] && flag[(i-1)*board[0].size() + j] ==0){
flag[(i - 1)*board[0].size() + j] = 1;//set the related flag to 1
if (n==word.size()-1)return true;
else if(judge(board, i-1, j, word, n+1, flag)) return true;//tract back
else flag[(i - 1)*board[0].size() + j] = 0; //clear flag
}
//check board[i,j+1]
if (j + 1 <= board[0].size() - 1 && board[i][j + 1] == word[n] && flag[i*board[0].size() + j+1] ==0){
flag[i*board[0].size() + j + 1] = 1;
if (n == word.size() - 1)return true;
else if (judge(board, i, j+1, word, n + 1, flag)) return true;
else flag[i*board[0].size() + j+1] = 0;
}
//check board[i+1,j]
if (i + 1 <= board.size() - 1 && board[i + 1][j] == word[n] && flag[(i+1)*board[0].size() + j] == 0){
flag[(i+1)*board[0].size() + j] = 1;
if (n == word.size() - 1)return true;
else if (judge(board, i + 1, j, word, n + 1, flag)) return true;
else flag[(i + 1)*board[0].size() + j] = 0;
}
//check board[i,j-1]
if (j - 1 >= 0 && board[i][j - 1] == word[n] && flag[i*board[0].size() + j - 1] ==0){
flag[i*board[0].size() + j - 1]=1;
if (n == word.size() - 1)return true;
else if (judge(board, i, j-1, word, n + 1, flag)) return true;
else flag[i*board[0].size() + j - 1]=0;
}
return false;
}
};
A better method to 'remember' the used char in the board is to set them to some char like '+' or '.', and keep the original char with a single variable.
///// 19ms////////////////////////
class Solution {
public:
bool BT(vector<vector<char>>& board, int row, int col, string &word, int idx){
if (idx==word.size()-1)return true;
else{
//left
if(col-1>=0 && board[row][col-1]==word[idx+1]){
char tmp=board[row][col-1];
board[row][col-1]='.';//set as '.' to prevent matching
if (BT(board, row, col-1, word, idx+1))return true;
board[row][col-1]=tmp;
}
//right
if(col+1<board[0].size() && board[row][col+1]==word[idx+1]){
char tmp=board[row][col+1];
board[row][col+1]='.';//set as '.' to prevent matching
if (BT(board, row, col+1, word, idx+1))return true;
board[row][col+1]=tmp;
}
//up
if(row-1>=0 && board[row-1][col]==word[idx+1]){
char tmp=board[row-1][col];
board[row-1][col]='.';//set as '.' to prevent matching
if (BT(board, row-1, col, word, idx+1))return true;
board[row-1][col]=tmp;
}
//down
if(row+1<board.size() && board[row+1][col]==word[idx+1]){
char tmp=board[row+1][col];
board[row+1][col]='.';//set as '.' to prevent matching
if (BT(board, row+1, col, word, idx+1))return true;
board[row+1][col]=tmp;
}
return false;
}
}
bool exist(vector<vector<char>>& board, string word) {
for (int r=0;r<board.size();r++){
for(int c=0;c<board[0].size();c++){
if (board[r][c]==word[0]){
char tmp=board[r][c];
board[r][c]='.';
if(BT(board, r, c, word, 0))return true;
//else return false;
board[r][c]=tmp;
}
}
}
return false;
}
};
No comments:
Post a Comment