d****o
发帖数: 1055 | 1 我完成了一个版本，可以过small test,但是过不了large test。
1. 请问我的版本的时间复杂度是多少？
2. 哪位有更好得解法，请教一下。
bool wordSearch(vector > &board, string word, int level,
vector >& used, int curRow, int curCol)
{
if(curRow<0||curRow>=board.size()||curCol<0||curCol>=board[0].size()
){
return false;
}
if(used[curRow][curCol])
return false;
if(board[curRow][curCol]!=word[level])
return false;
if(level==word.size()-1){
cout<
cout<
return true;
}
used[curRow][curCol]=1;
bool res1=wordSearch(board,word,level+1,used,curRow+1,curCol);
bool res2=wordSearch(board,word,level+1,used,curRow-1,curCol);
bool res3=wordSearch(board,word,level+1,used,curRow,curCol+1);
bool res4=wordSearch(board,word,level+1,used,curRow,curCol-1);
used[curRow][curCol]=0;
return res1||res2||res3||res4;
}
bool exist(vector > &board, string word) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int ROW = board.size();
int COL = board[0].size();
vector > used(ROW, vector(COL,0));
for(int i=0;i
for(int j=0;j
if(wordSearch(board,word,0,used,i,j))
return true;
}
}
return false;
} |
|
