# My 19ms accepted C++ code

• ``````   class Solution {
public:
bool exist(vector<vector<char> > &board, string word) {
m=board.size();
n=board[0].size();
for(int x=0;x<m;x++)
for(int y=0;y<n;y++)
{
if(isFound(board,word.c_str(),x,y))
return true;
}
return false;
}
private:
int m;
int n;
bool isFound(vector<vector<char> > &board, const char* w, int x, int y)
{
if(x<0||y<0||x>=m||y>=n||board[x][y]=='\0'||*w!=board[x][y])
return false;
if(*(w+1)=='\0')
return true;
char t=board[x][y];
board[x][y]='\0';
if(isFound(board,w+1,x-1,y)||isFound(board,w+1,x+1,y)||isFound(board,w+1,x,y-1)||isFound(board,w+1,x,y+1))
return true;
board[x][y]=t;
return false;
}
};``````

• Great work! But the board is destroyed.

• I have a similar solution but it isn't as clean as yours. I use another 2D array to record the route.

class Solution {
public:

``````bool helper(int statr,int statc,vector<vector<char> > &board,string word, vector<vector<bool> > &route){

if(word == "") return true;

int rows = board.size();
int cols = board[0].size();

route[statr][statc]=true;

while(statr <rows && statc <cols){
//up
if(statr-1>=0 && !route[statr-1][statc] && word[0] == board[statr-1][statc])
if(helper(statr-1,statc,board,word.substr(1,word.length()-1), route))
return true;
else {

route[statr-1][statc] = false;
}
//down
if(statr+1<rows && !route[statr+1][statc] && word[0] == board[statr+1][statc])
if(helper(statr+1,statc,board,word.substr(1,word.length()-1), route))
return true;
else {

route[statr+1][statc] = false;
}
//left
if(statc-1>=0 && !route[statr][statc-1] && word[0] == board[statr][statc-1])
if(helper(statr,statc-1,board,word.substr(1,word.length()-1), route))
return true;
else {

route[statr][statc-1] = false;
}
//right
if(statc+1<cols && !route[statr][statc+1] && word[0] == board[statr][statc+1])
if(helper(statr,statc+1,board,word.substr(1,word.length()-1), route))
return true;
else {

route[statr][statc+1] = false;
}
break;
}

return false;
}

bool exist(vector<vector<char> > &board, string word) {

if(word == "") return true;
if(board.empty()) return false;

int rows = board.size();
int cols = board[0].size();

vector<vector<bool> >route(rows, vector<bool>(cols,false));

for(int i=0; i<rows; ++i)
{
for(int j=0; j<cols; j++)
{
if(board[i][j] == word[0])
if(helper(i,j,board,word.substr(1,word.length()-1),route))
return true;
else route[i][j]=false;
}
}

return false;
}
``````

};

• not as faster as the above, right?

• Why the "while" and then "break" instead of "if"?

• Good solution! I am just wonder how you test the running time of your solution? under which enviroment? Thanks!

• I don't think so.. It will be recover when "board[x][y]=t;" after the sub-recursion.
"board[x][y]='\0';" is just for the judgement that board[x][y]=='\0' in "if(x<0||y<0||x>=m||y>=n||board[x][y]=='\0'||*w!=board[x][y])".

• You are right. I should use if instead~

• My code is easy to understand but can not as fast and clean as the above one.

• Mine? After you submit your code, you can press the details button and it will show the running time.

• Actually he is right. If the word is successfully found, the data of the table will be changed and cannot be used again for another search.

• i guess setting it to t before returning 'true' solves the problem

• Yes U are right. It is a interesting bug, but it can be fixed by the next comment said easily...

• Yeah, I think you are right !~

• This post is deleted!

• can you please mention space and time complexity?

• Just store the result in bool and recover the board and then return the bool instead of directly returning the function call.

• My accepted non-recursive backtrace solution using stack:

https://discuss.leetcode.com/topic/53468/ac-non-recursive-backtrace-solution-with-stack

• I found a really strange problem is, when I delete the "&" in the function isFound, the runtime will exceed the limit, is there anyone knows why is this? the answer is still correct but takes much more time.

• @greenup

``````class Solution {
private:
vector<vector<char>> boardTemp;
string wordTemp;
public:
bool exist(vector<vector<char>>& board, string word) {
boardTemp=board;
wordTemp=word;
if(boardTemp.size()==0)return false;
if(word.compare("")==0)return true;
for(int i=0;i<boardTemp.size();i++){
for(int j=0;j<boardTemp[i].size();j++)
if(check(i,j,0)) return true;
}
return false;
}

bool check(int x,int y,int start){
if(start>=wordTemp.size())return true;
if(x<0||x>=boardTemp.size()||y<0||y>=boardTemp[x].size())return false;
if(boardTemp[x][y]!=wordTemp[start])return false;
char c=boardTemp[x][y];