Princeton Algorithm Assignment Boggle
普林斯顿大学算法课 Boggle
实现一个 Boggle 游戏，由自己决定采用什么数据结构和搜索方法。
基本就是字典树（Trie）的实际应用。
提供了 BogleBoard 类和 BoggleGame 类，可以很方便把自己写的 Solver 给整合进去，直接编译成可以玩的游戏，顺便也验证一下结果是否正确。
Trie 的正确实现不难，DFS 也很无脑，基本可以轻松拿到 80 到 90 分，主要是性能上的优化，想要拿满分（甚至 bonus），需要考虑：
- 回溯优化：当某一个结点的没有孩子的时候，不需要进行 DFS；
if (node.hasChild()) {
for (int x = -1; x <= 1; x++) {
for (int y = -1; y <= 1; y++) {
int newRow = row + x;
int newCol = col + y;
if (isValid(board, newRow, newCol) && !visited[newRow][newCol]) {
dfs(board, newRow, newCol, visited, node);
}
}
}
}
- 单词只包含 A 到 Z，所以直接使用 26 个结点的 Trie，比 TNT 快很多（虽然占用了更多的内存）；
// Recall that the alphabet consists of only the 26 letters A through Z
// Use trie 26, more space but faster than TNT
links = new TrieNode[26];
- DFS 中的前缀查询，通常会得到一致的结果, 只是每次长了一个字符，所以不需要每一次都进行前缀查询，保存 TrieNode 的状态，在每一次 DFS 中更新；
public TrieNode prefixNode(char c, TrieNode cache) {
if (cache == null) {
cache = root;
}
if (cache.contains(c)) {
cache = cache.get(c);
} else {
return null;
}
return cache;
}
- 由于 Q 之后只会包含 u，不存在 Qx 的情况，所以没必要在 Trie 中存储 Qu，只需要 Q 就可以了，处理时特判 Q，跳过 u；
if (c == 'Q') {
i++; // Skip "Qu"
if (i == word.length() || word.charAt(i) != 'U') {
// Ignore "Q" and "Qx"
return false;
}
}
i++;
- 不要使用 Set，在 TrieNode 中增加一个标记，表示这个单词是否被添加过，例如当访问过了之后修改这个 TrieNode 的 added 为 true，但是注意，我们会对同一个字典（Trie）执行多次 getAllValidWords，所以仅用 true/false 不足以表示这样的情况，我们在 TrieNode 中增加一个 uid 字段，每次执行 getAllValidWords 时增加 uid，判断在当前 uid 下，这个单词是不是被加入过；
public Iterable<String> getAllValidWords(BoggleBoard board) {
answers = new ArrayList<>();
uid++;
// DFS
return new ArrayList<>(answers);
}
if (node.isEnd() && node.getUid() != uid) {
String word = node.getWord();
if (word.length() > 2) {
answers.add(word);
node.setUid(uid);
}
}
- 不要在 DFS 中用类似 StringBuilder 的东西，在 Trie 中构造字符串，并存在 TrieNode 中，因为 Trie 只会被构建一次，这样之后 DFS 直接根据 Node 中的字符串输出单词，就会快很多。
参考解决方案的每秒查询数大概在 8000 次左右，要求 reference/student ratio 小于等于 2，即实现方案的每秒查询数大于 4000 就可以得到满分，上面这些方案的任意组合足以达到 ratio <= 1，即每秒查询 8000 次以上。
如果还想要获得 Bonus（ratio <= 0.5，即每秒查询 16000 次以上），需要额外处理：
Precompute the Boggle graph, i.e., the set of cubes adjacent to each cube. But don't necessarily use a heavyweight Graph object: To caculate the key for every point, which means key = y * width + x, then for every point, save current key's neighbors key in int[][] graph , therefore we need a letter array to map the key to the letter in board.
以下代码获得 Coursera 评分 100 分：访问 GitLab仓库、GitHub仓库 和/或 博客 查看完整代码。
