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. Example:
Input Board :
{
{A, O, L},
{D, E, L},
{G, H, I},
}
Dictionary : [HELLO, HOW, ARE, YOU] (as a Trie)
Output: [HELLO]
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** ! 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. TreeSet
to store the words and convert it to an ArrayList
at the end.
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.if( r > rows-1
|| r < 0
|| c > cols-1
|| c < 0
|| !dictionary.searchPrefix(prefix)
|| board[r][c] is visited){
return;
}
class TrieNode {
Character c;
Boolean isLeaf = false;
HashMapchildren = 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;
HashMapchildren = 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;
HashMapchildren = 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;
HashMapchildren = 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;
}
}
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. ; 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> boggleByot(char[][] board, ArrayList<String> dictionary){ }
C
Java
Python