char[][] board
, and a String - word
. Write a method - boggleSearch
that searches the Boggle Board for the presence of the input word
. Words on the board can be constructed with sequentially adjacent letters, where adjacent letters are horizontal or vertical neighbors (not diagonal). Also, each letter on the Boggle Board must be used only once. Example:
Input Board :
{
{A, O, L},
{D, E, L},
{G, H, I},
}
Word: "HELLO"
Output: true
search
that will be called from the wrapper method - boggleSearch
. We need to store enough information in each recursion stack frame to create the next frame. Therefore, the helper method signature can look like this :public static boolean search(int r, int c, char[][] board, String word, String predecessor)
if( r > rows-1
|| r < 0
|| c > cols-1
|| c < 0
|| !word.contains(predecessor)
|| board[r][c] is visited){
return false;
}
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
out = search(i,j,board,word,"");
if(out) return true;
}
}
public static boolean search(int r, int c, char[][] board, String word, String predecessor)
board[r][c] = specialChar;
out = search(r-1,c,board,word,s)
|| search(r+1,c,board,word,s)
|| search(r,c-1,board,word,s)
|| search(r,c+1,board,word,s);
board[r][c] = tempValue
out
to the caller.public static boolean boggleSearch(char[][] board, String word){ }
C
Java
Python