0079-word-search.cs

publicclassSolution
{
//T:O(N*M*4^LenOfWord), S: O(m+n+ L)
//S: O(m+n) is for the visited array
publicboolExist(char[][]board,stringword)
{
varrows=board.Length;
varcols=board[0].Length;
varvisited=newbool[rows,cols];

for(vari=0;i<rows;i++)
{
for(varj=0;j<cols;j++)
{
if(board[i][j]==word[0]&&search(i,j,0,word,board,visited))
returntrue;
}
}

returnfalse;
}

publicboolsearch(intr,intc,intindex,stringword,char[][]board,bool[,]visited)
{
varrows=board.Length;
varcols=board[0].Length;

if(index==word.Length)
returntrue;
if(r<0||c<0||r>=rows||c>=cols||word[index]!=board[r][c]||visited[r,c])
returnfalse;

visited[r,c]=true;
varresult=search(r+1,c,index+1,word,board,visited)||
search(r-1,c,index+1,word,board,visited)||
search(r,c+1,index+1,word,board,visited)||
search(r,c-1,index+1,word,board,visited);

visited[r,c]=false;
returnresult;

}

}