Boggle Search
You're given a 2D Boggle Board which contains an m x n matrix of chars -
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
Need a hand? Try out these hints, one at a time.
This is a classic DFS problem. You have the option to solve this iteratively or recursively, but considering the fact that you need to keep a track of your current path and possibly mark nodes as visited and not visited in the matrix, recursion yields a simpler and more elegant solution. To solve this problem recursively, create a helper method -
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)
Carefully construct your terminating conditions in the helper method. You want to terminate as soon as you begin searching outside the boundaries of the board, if the current node has already been visited or if the word being constructed does not match the input word :
if( r > rows-1
|| r < 0
|| c > cols-1
|| c < 0
|| !word.contains(predecessor)
|| board[r][c] is visited){
return false;
}
1) Iterate across all characters of the board in the wrapper method and call the helper search method for each character :
2) Create a helper method which will be called from the wrapper as well as recursively :
3) Define the terminating conditions and return false if any are met : See Hint 2.
4) Check if the word has been matched. If yes, return true.
5) Mark the current node as visited with some special character and store it's value somewhere -
6) Recursively call the helper method to search the top, bottom, left and right cells :
7) Unmark the visited node :
8) Return
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
out = search(i,j,board,word,"");
if(out) return true;
}
}2) Create a helper method which will be called from the wrapper as well as recursively :
public static boolean search(int r, int c, char[][] board, String word, String predecessor)
3) Define the terminating conditions and return false if any are met : See Hint 2.
4) Check if the word has been matched. If yes, return true.
5) Mark the current node as visited with some special character and store it's value somewhere -
board[r][c] = specialChar;6) Recursively call the helper method to search the top, bottom, left and right cells :
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);
7) Unmark the visited node :
board[r][c] = tempValue8) Return
out to the caller.
public static boolean boggleSearch(char[][] board, String word){
}
This Coding Interview Question is available with an answer in the following programming languages :
C
Java
Python