作业地址：http://coursera.cs.princeton.edu/algs4/assignments/boggle.html
作业难点：
1、如何保证求解速度，满分要求是求解速度 >= 0.5 * 参考速度，约在5000次/5s。
1）最直观的算法思想：要明确查找单词即为对一个游戏板（board）上的一个顶点向8个方向进行深度优先遍历，在遍历过程中查找单词是否在词典中，将在词典中的单词记录保存下来。为顺利找出所有满足条件的单词，可以使用广度、深度优先遍历该顶点。重复遍历完所有顶点即可找出在词典中的所有单词。
2）根据算法思想构建数据结构：游戏板-board[][]一个二维数组，构建词典使用教材提及的TST（三叉单词查找树）或者Trie（单词查找树），保存已找出的单词（因为按题目要求重复单词只保留一个）使用HashSet，遍历方法采用dfs（深度优先搜索）方法。
3）根据dfs原理构建算法求解，使用marked[][]标记已访问的顶点，使用TST构建词典，求解速度约在2500次/5s，需要优化。
4）为避免回溯过程中重复查找单词树，为TST新增一个hasPrefix(String key)函数（查找单词树中是否包含key前缀），返回TST的Node类型：root——未查找到，非root——查找到。因为返回的是Node，所以每次只需查找Node以后的枝叶即可，key也即board[i][j]的字母即可。此时，求解速度约在3500次/5s，需要优化。
5）弃用TST，改用Trie构建词典，修改hasPrefix()函数为getNext(String key)函数，此时求解速度上次到6500次/5s，可以满分，离参考值还有一段距离。
6）因为查找的过程中存在重复单词，所以在开始的时候使用HashSet来保存找到的单词，存在查找重复单词并将其重复插入的情况。为避免对重复单词进行多次处理，设置处理过的单词的val值为-1，并记录该节点的位置，将其保存下来，在处理的最后对节点的val进行恢复。没有了重复单词，也就不需要HashSet来保存查找到的单词，使用简单的链表来保存即可，保存单词的速度更快。此时求解速度可以上升到10000次/5s。
容易扣分点：
同作业难点。
部分代码：
1、数据结构：
private Trie dict; private String[][] gameStr; private Bag<String> words; // found words private Bag<Trie.Node> nodes; // nodes of found words private static class Trie { private static int R = 26; // Radix, English alphabet private static final int OFFSET = ‘A‘;
public Node root; class Node { int val; Node[] next = new Node[R]; }
}
2、getAllValidWords(BoggleBoard board)：
public Iterable<String> getAllValidWords(BoggleBoard board) { words = new Bag<String>(); nodes = new Bag<Trie.Node>(); int col = board.cols(), row = board.rows(); boolean[][] marked = new boolean[row][col]; gameStr = new String[row][col]; for (int i = 0; i < row; i++) for (int j = 0; j < col; j++) gameStr[i][j] = representQ(i, j, board); for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { Trie.Node pNode = dict.getNext(dict.root, gameStr[i][j]); if (pNode != null) dfs(board, marked, i, j, pNode, gameStr[i][j]); } } for (Trie.Node n : nodes) n.val = 1; return words; } private void dfs(BoggleBoard board, boolean[][] marked, int x, int y, Trie.Node pNode, String preStr) { marked[x][y] = true; String curStr; int xNeighbor, yNeighbor; Trie.Node queryNode; if (pNode.val == 1 && preStr.length() > 2) { words.add(preStr); nodes.add(pNode); pNode.val = -1; } for (int i = 0; i < XDELTA.length; i++) { xNeighbor = x + XDELTA[i]; yNeighbor = y + YDELTA[i]; if (validPos(xNeighbor, yNeighbor, board) && !marked[xNeighbor][yNeighbor]) { queryNode = dict.getNext(pNode, gameStr[xNeighbor][yNeighbor]); if (queryNode != null) { curStr = preStr + gameStr[xNeighbor][yNeighbor]; dfs(board, marked, xNeighbor, yNeighbor, queryNode, curStr); } } } marked[x][y] = false; }
原文：http://www.cnblogs.com/notTao/p/6389629.html
