Princeton Algorithm Assignment Boggle
普林斯頓大學算法課 Boggle
實現(xiàn)一個 Boggle 游戲玄括，由自己決定采用什么數(shù)據(jù)結構和搜索方法液荸。
基本就是字典樹（Trie）的實際應用岸蜗。
提供了 BogleBoard 類和 BoggleGame 類，可以很方便把自己寫的 Solver 給整合進去绊袋，直接編譯成可以玩的游戲，順便也驗證一下結果是否正確铸鹰。
Trie 的正確實現(xiàn)不難癌别，DFS 也很無腦，基本可以輕松拿到 80 到 90 分蹋笼，主要是性能上的優(yōu)化展姐，想要拿滿分（甚至 bonus），需要考慮：
- 回溯優(yōu)化：當某一個結點的沒有孩子的時候剖毯，不需要進行 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 的狀態(tài)，在每一次 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）執(zhí)行多次 getAllValidWords拷况，所以僅用 true/false 不足以表示這樣的情況作煌，我們在 TrieNode 中增加一個 uid 字段掘殴，每次執(zhí)行 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 直接根據(jù) Node 中的字符串輸出單詞悲酷，就會快很多套菜。
參考解決方案的每秒查詢數(shù)大概在 8000 次左右，要求 reference/student ratio 小于等于 2设易，即實現(xiàn)方案的每秒查詢數(shù)大于 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倉庫 和/或 博客 查看完整代碼旷祸。
