Boggle with Electronic Dictionary
You're given a 2D Boggle Board which contains an m x n matrix of chars -
Note: The Trie has two built-in methods that you'll find useful for this problem -
char[][] board, and a fast, electronic Dictionary in the form of a Prefix Tree or Trie. Write a method - boggleSearchWithDict that searches the Boggle Board for words in the dictionary. Your method should return an alphabetically sorted ArrayList of words that are present on the board as well as in the dictionary. 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. Your program should run in a reasonable amount of time (at max about 50 ms for each test case) and shouldn't time out. Note: The Trie has two built-in methods that you'll find useful for this problem -
searchWord(String s) and searchPrefix(String s). These will return true if the complete word or prefix are found in the dictionary, respectively.Example:
Input Board :
{
{A, O, L},
{D, E, L},
{G, H, I},
}
Dictionary : [HELLO, HOW, ARE, YOU] (as a Trie)
Output: [HELLO]
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 -
Since your output must be lexically sorted, consider using a
Use the
search that will be called from the wrapper method - boggleSearchWithDict. We need to store enough information in each recursion stack frame to create the next frame. Since your output must be lexically sorted, consider using a
TreeSet to store the words and convert it to an ArrayList at the end. Use the
searchPrefix(String s) and searchWord(String s) methods on the Trie to limit your search to a reasonable complexity.
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 any words in the dictionary :
if( r > rows-1
|| r < 0
|| c > cols-1
|| c < 0
|| !dictionary.searchPrefix(prefix)
|| board[r][c] is visited){
return;
}
Create a
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 if any are met : See Hint 2.
4) Check if the prefix is a word in the dictionary with
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) Convert the
TreeSet - outputHolder to store the intermediate words that are found ; 1) Iterate across all characters of the board in the wrapper method and call the helper search method for each character :
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
search(i,j,board,dictionary,"",outputHolder);
}
}2) Create a helper method which will be called from the wrapper as well as recursively :
public void search(int r, int c, char[][] board, Trie dictionary, String prefix, TreeSet outputHolder)
3) Define the terminating conditions and return if any are met : See Hint 2.
4) Check if the prefix is a word in the dictionary with
searchWord(String word). If yes, add it to outputHolder.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 :
search(r-1,c,board,dictionary,s,outputHolder);
search(r+1,c,board,dictionary,s,outputHolder);
search(r,c-1,board,dictionary,s,outputHolder);
search(r,c+1,board,dictionary,s,outputHolder);
7) Unmark the visited node :
board[r][c] = tempValue8) Convert the
TreeSet to an ArrayList and return it : return new ArrayList(outputHolder)
public ArrayList<String> boggleSearchWithDict(char[][] board, Trie dictionary){
}
This Coding Interview Question is available with an answer in the following programming languages :
C
Java
Python