Question
Boggle Game:
F X I E
A M L O
E W B X
A S T U
The goal of the game is to find as many words as you can that can be formed by chaining letters together. You are given a dictionary of words are reference.
Solution
The best solution is to use Trie, then do DFS search.
The idea is from this answer (however, this guy said his solution does not handle ‘visited’ nodes properly, meaning that same char might be visited again to produce a word).
We need to first define a class called Item:
class Item {
public final int x, y;
public final String prefix;
public Item(int row, int column, String prefix) {
this.x = row;
this.y = column;
this.prefix = prefix;
}
}
So when we start doing DFS, we pass in an Item object which stores 2 information:
- The next position that we’re going to visit.
- The prefix string that we have validated so far (before visiting this position).
For example:
F X I E
A M L O
E W B X
A S T U
We’ll have Items objects like (0, 0, “”), (0, 1, “F”), (0, 2, “FA”) … We guarantee that the prefix must be a valid prefix by searching them in the Trie.
How to tell whether a string is a prefix of word, or it’s an actual word? We have a property in TrieNode called TrieNode.isWord() to help us.
The code I wrote below is based on this Java solution by zouzhile.
Code
BoggleSolver.java
public class BoggleSolver {
private static BufferedReader in = null;
private static final String INPUT_FILE = "dictionary.txt";
public static void beginFileReader() {
try {
in = new BufferedReader(new FileReader(new File(BoggleSolver.class
.getResource(INPUT_FILE).toURI())));
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (URISyntaxException e) {
e.printStackTrace();
}
}
private Trie buildTrie() {
Trie trie = new Trie();
beginFileReader();
String line = null;
try {
while ((line = in.readLine()) != null) {
String[] words = line.split(" ");
for (String word : words) {
word = word.trim().toLowerCase();
trie.addWord(word);
}
}
if (in != null) {
in.close();
}
} catch (IOException e1) {
e1.printStackTrace();
}
return trie;
}
public Set<String> findWords(char[][] map, Trie dict) {
Set<String> ans = new TreeSet<String>();
int m = map.length;
int n = map[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
boolean[][] visited = new boolean[m][n];
findWordsDfs(ans, dict, map, visited, new Item(i, j, ""));
// item have 3 parameters:
// location x,y and the prefix string before reaching (i.j)
}
}
return ans;
}
public void findWordsDfs(Set<String> ans, Trie dict, char[][] map,
boolean[][] visited, Item item) {
// item: the location that we're going to test
// item.prefix is the word prefix before reaching (x, y)
int m = map.length;
int n = map[0].length;
int x = item.x;
int y = item.y;
// check whether cur.(x,y) is a valid position
if (x < 0 || x >= m || y < 0 || y >= n) {
return;
} else if (visited[x][y]) {
return;
}
String newWord = item.prefix + map[x][y];
// check whether cur.prefix is a valid prefix
TrieNode findWord = dict.match(newWord);
if (findWord == null) {
// up to this position (x, y), the word dont' exists
return;
}
// now cur is in a valid position, with a valid prefix
if (findWord.isWord()) {
ans.add(newWord);
}
// visit this position, and continue in 4 different directions
visited[x][y] = true;
findWordsDfs(ans, dict, map, visited, new Item(x, y - 1, newWord));
findWordsDfs(ans, dict, map, visited, new Item(x, y + 1, newWord));
findWordsDfs(ans, dict, map, visited, new Item(x - 1, y, newWord));
findWordsDfs(ans, dict, map, visited, new Item(x + 1, y, newWord));
visited[x][y] = false;
}
public static void main(String[] args) {
String[] rows = "eela,elps,weut,korn".split(",");
char[][] input = new char[4][4];
for (int i = 0; i < 4; i++) {
input[i] = rows[i].toCharArray();
}
// prepare test data
BoggleSolver solver = new BoggleSolver();
Trie dictionary = solver.buildTrie();
// start finding words
Set<String> set = solver.findWords(input, dictionary);
// present the result
System.out.println(set.size() + " words are found, they are: ");
for (String str : set) {
System.out.println(str);
}
}
class Item {
public final int x, y;
public final String prefix;
public Item(int row, int column, String prefix) {
this.x = row;
this.y = column;
this.prefix = prefix;
}
}
}
Trie.java
public class Trie {
private TrieNode root;
public Trie() {
this.root = new TrieNode();
}
public void addWord(String word) {
TrieNode node = this.root;
for (char c : word.toCharArray()) {
node = node.addChild(c);
if (node == null)
return;
}
node.setWord(true);
}
public TrieNode match(String s) {
TrieNode node = this.root;
for (char c : s.toCharArray()) {
node = node.get(c);
if (node == null)
return null;
}
return node;
}
}
TrieNode.java
public class TrieNode {
private TrieNode[] children;
private boolean isWord = false;
public TrieNode() {
this.children = new TrieNode[26];
}
public TrieNode addChild(char child) {
if (child < 'a' || child > 'z')
return null;
int offset = child - 'a';
if (this.children[offset] == null) {
this.children[offset] = new TrieNode();
}
return this.children[offset];
}
public boolean isWord() {
return isWord;
}
public void setWord(boolean isWord) {
this.isWord = isWord;
}
public TrieNode get(char c) {
int offset = c - 'a';
return this.children[offset];
}
}