|
| 1 | +/* |
| 2 | +Given an m x n grid of characters board and a string word, return true if word exists in the grid. |
| 3 | +Time: O(n*m*(3^h)) where h is the length of the word |
| 4 | +Space: O(1) |
| 5 | +
|
| 6 | +*/ |
| 7 | + |
| 8 | +booldfs(char**board,intn,intm,inti,intj,char*word) { |
| 9 | +if (word[0]=='\0'||word[1]=='\0') |
| 10 | +return true; |
| 11 | +charc=board[i][j]; |
| 12 | +board[i][j]=0; |
| 13 | +if (i>0&&board[i-1][j]==word[1]){ |
| 14 | +if (dfs(board,n,m,i-1,j,word+1)){ |
| 15 | +board[i][j]=c; |
| 16 | +return true; |
| 17 | + } |
| 18 | + } |
| 19 | +if (j>0&&board[i][j-1]==word[1]){ |
| 20 | +if (dfs(board,n,m,i,j-1,word+1)){ |
| 21 | +board[i][j]=c; |
| 22 | +return true; |
| 23 | + } |
| 24 | + } |
| 25 | +if (i<(n-1)&&board[i+1][j]==word[1]){ |
| 26 | +if (dfs(board,n,m,i+1,j,word+1)){ |
| 27 | +board[i][j]=c; |
| 28 | +return true; |
| 29 | + } |
| 30 | + } |
| 31 | +if (j<(m-1)&&board[i][j+1]==word[1]){ |
| 32 | +if (dfs(board,n,m,i,j+1,word+1)){ |
| 33 | +board[i][j]=c; |
| 34 | +return true; |
| 35 | + } |
| 36 | + } |
| 37 | +board[i][j]=c; |
| 38 | +return false; |
| 39 | +} |
| 40 | + |
| 41 | + |
| 42 | +boolexist(char**board,intboardSize,int*boardColSize,char*word){ |
| 43 | +intm= (*boardColSize),i,j; |
| 44 | +for (i=0;i<boardSize;i++) { |
| 45 | +for (j=0;j<m;j++) { |
| 46 | +if (board[i][j]==word[0]) { |
| 47 | +if (dfs(board,boardSize,m,i,j,word)){ |
| 48 | +return true; |
| 49 | + } |
| 50 | + } |
| 51 | + } |
| 52 | + } |
| 53 | +return false; |
| 54 | +} |