Boggle with Paper Dictionary
You're given a 2D Boggle Board which contains an m x n matrix of chars -
Note:
Your program should run in a reasonable amount of time - about a few milliseconds for each test case.
char[][] board, and a rudimentary, paper Dictionary in the form of an ArrayList of close to 10,000 words. Write a method - boggleByot 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. Note:
Your program should run in a reasonable amount of time - about a few milliseconds for each test case.
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.
The dictionary provided with this problem is an
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
ArrayList that can have thousands of numbers. It will be very, very expensive to use this dictionary as-is, and that's your biggest hint for this problem. BYOT - Bring Your Own Tr** ! 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 - boggleByot. 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.
Before you begin writing the algorithm for the search, create a
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 :
Trie class that provides the required functionality - searchPrefix(String prefix) and searchWord(String word). If you're stuck or unfamiliar with creating a Trie, click on Use Me and check out the class structure.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;
}
Constructing the Trie:
Algorithm:
Before we begin, add all the words from the
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
class TrieNode {
Character c;
Boolean isLeaf = false;
HashMap children = new HashMap<>();
public TrieNode(){}
public TrieNode(Character c){
this.c = c;
}
}
class Trie {
private TrieNode root;
public Trie(){
this.root = new TrieNode();
}
public void insertWord(String word){
TrieNode cur = root;
HashMap children = cur.children;
for(int i=0; i < word.length(); i++){
char c = word.charAt(i);
if(children.containsKey(c)){
cur = children.get(c);
} else {
TrieNode n = new TrieNode(c);
children.put(c,n);
cur = n;
}
children = cur.children;
if(i == word.length()-1) cur.isLeaf = true;
}
}
public Boolean searchWord(String word){
TrieNode cur = root;
HashMap children = cur.children;
for(int i=0; i < word.length(); i++){
char c = word.charAt(i);
if(children.containsKey(c)){
cur = children.get(c);
children = cur.children;
} else return false;
}
return cur.isLeaf;
}
public Boolean searchPrefix(String word) {
TrieNode cur = root;
HashMap children = cur.children;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (children.containsKey(c)) {
cur = children.get(c);
children = cur.children;
} else {
return false;
}
}
return true;
}
} Algorithm:
Before we begin, add all the words from the
ArrayList to your custom Trie and use this Trie as your dictionary going forward. Also, create a 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> boggleByot(char[][] board, ArrayList<String> dictionary){
}
This Coding Interview Question is available with an answer in the following programming languages :
C
Java
Python