# [C++] why is my solution time exceed? Can somebody find the problem?

• ``````bool isfind(int row, int col, int pos, const vector<vector<char>>& board,
const string& word,vector<vector<bool>> &trace){
//dir:the direction into this cell, up:1,down:-1;left:-2,right:2,none:0
if(pos == word.size()) return true;
if(row < 0 || col < 0 || row >= board.size() || col >= board[0].size()) return false;
if(board[row][col] != word[pos]) return false;

bool result = false;
trace[row][col] = true;

if(row - 1 >= 0 && trace[row-1][col] == false )
result = result || isfind(row-1, col, pos+1,board,word,trace); //up
if(row + 1 < board.size() && trace[row+1][col] == false )
result = result || isfind(row+1, col, pos+1,board,word,trace);  //down
if(col - 1 >= 0 && trace[row][col-1] == false )
result = result || isfind(row, col-1, pos+1,board,word,trace); //left
if(col + 1 < board[0].size() && trace[row][col+1] == false )
result = result || isfind(row, col+1, pos+1,board,word,trace); //right

if(!result) trace[row][col] = false;

return result;
}
bool exist(vector<vector<char>>& board, string word) {
if(word.empty()) return true;
vector<vector<bool> > trace(board.size(), vector<bool>(board[0].size(),false));
for(int row = 0; row < board.size(); ++row)
for(int col = 0; col < board[0].size();++col)
if(board[row][col] == word[0] && isfind(row,col,0,board,word,trace))
return true;
return false;
}``````

• A few things. 1: You don't need to create a new trace vector, you can modify the original board to mark visited spot and change it back later. I suspect your original code did not work since creating a new trace vector takes awhile? 2. You don't have to check for " if(row - 1 >= 0 && trace[row-1][col] == false )", since you have already done so in the beginning in "if(row < 0 || col < 0 || row >= board.size() || col >= board[0].size()) return false;" 3. In my version I repeated the if(!result) 4 times. You can try to come up with a better way to do that.

``````class Solution {
public:
bool isfind(int row, int col, int pos, vector<vector<char>>& board,
string& word){
//dir:the direction into this cell, up:1,down:-1;left:-2,right:2,none:0
if(pos == word.size()) return true;
if(row < 0 || col < 0 || row >= board.size() || col >= board[0].size()) return false;
if(board[row][col] != word[pos]) return false;

bool result = false;
board[row][col] = ' ';
if(!result)
result = isfind(row-1, col, pos+1,board,word); //up
if(!result)
result = isfind(row+1, col, pos+1,board,word);  //down
if(!result)
result = isfind(row, col-1, pos+1,board,word); //left
if(!result)
result = isfind(row, col+1, pos+1,board,word); //right
board[row][col] = word[pos];

return result;
}
bool exist(vector<vector<char>>& board, string word) {
if(word.empty()) return true;

for(int row = 0; row < board.size(); ++row)
for(int col = 0; col < board[0].size();++col)
if(board[row][col] == word[0] && isfind(row,col,0,board,word))
return true;
return false;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.