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. 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]
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. TreeSet
to store the words and convert it to an ArrayList
at the end. searchPrefix(String s)
and searchWord(String s)
methods on the Trie to limit your search to a reasonable complexity.
if( r > rows-1
|| r < 0
|| c > cols-1
|| c < 0
|| !dictionary.searchPrefix(prefix)
|| board[r][c] is visited){
return;
}
TreeSet
- outputHolder
to store the intermediate words that are found ; for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
search(i,j,board,dictionary,"",outputHolder);
}
}
public void search(int r, int c, char[][] board, Trie dictionary, String prefix, TreeSet outputHolder)
searchWord(String word)
. If yes, add it to outputHolder
.board[r][c] = specialChar;
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);
board[r][c] = tempValue
TreeSet
to an ArrayList
and return it : return new ArrayList(outputHolder)
public ArrayList<String> boggleSearchWithDict(char[][] board, Trie dictionary){ }
C
Java
Python