任务连接:http://coursera.cs.princeton.edu/algs4/assignments/boggle.htmlhtml
此次任务给的须要实现的方法不多,完成本次任务关键在于理清思路,须要实现较多的私有方法。java
须要本身设计单词树,将单词树中每一个字符节点定义为一个类。node
private static class Node // 字典中节点类 { private boolean isWord; // 到达该节点是否为单词标志位 private Node[] next = new Node[R]; // 该节点的后继节点 }
该单词节点类有一个标志位,表示从头节点到该节点所构成字符序列为一个单词。next数组表示该字符以后接下来可能出现的26个字符节点类。数组
另外设计一个存储相邻节点下标的类,用于存储该节点在面板中相邻的8个(最多)方向的字符的下标,并用n标记真实数组的长度数据结构
private static class Adjacent // 游戏面板相邻节点类 { private int n = 0; // 相邻节点数组长度 private int[] neighbor = new int[8]; // 相邻节点 }
设计步骤:app
首先,咱们须要为给定的单词词集设计成单词树。ui
而后对面板的字符采用DFS方法进行组成字符序列查找单词树。当查到单词树的叶子节点时就中止本次查找。和以前的DFS不一样的时,在对mark数组进行处理的时候,在退出递归查找以前需将给位置mark设置为false,以便别的单词序列能包含该字符。设计
其中为了节省时间,需提早计算好每一个位置上的字符相邻字符的下标。即利用上面的Adjacent类。code
import edu.princeton.cs.algs4.In; import edu.princeton.cs.algs4.SET; import edu.princeton.cs.algs4.StdOut; public class BoggleSolver { private static final int R = 26; // A-Z private boolean[][] marked; // 游戏面板遍历标志位 private char[][] boardChar; // 游戏面板存放字符 private Adjacent[] adjacents; // 相邻节点数组 private int row; // 行 private int col; // 列 private Node root; // 字典根节点 private static class Node // 字典中节点类 { private boolean isWord; // 到达该节点是否为单词标志位 private Node[] next = new Node[R]; // 该节点的后继节点 } private static class Adjacent // 游戏面板相邻节点类 { private int n = 0; // 相邻节点数组长度 private int[] neighbor = new int[8]; // 相邻节点 } // 使用给定的字符串数组做为字典初始化数据结构。 // (你能够假设字典中的每一个单词只包含大写字母A到Z)。 public BoggleSolver(String[] dictionary) { if (dictionary == null) throw new java.lang.IllegalArgumentException("the string[] is null"); // 依次添加进字典中 for (int i = 0; i < dictionary.length; i++) addToDictionary(dictionary[i]); } // 将单词插入字典中 private void addToDictionary(String word) { if (word == null) throw new java.lang.IllegalArgumentException("the string is null"); root = add(root, word, 0); } // 对单词的字符进行操做 private Node add(Node x, String word, int d) { if (x == null) x = new Node(); if (d == word.length()) // 到达单词结尾时,在对应的字符节点处设置为是单词标志 x.isWord = true; else { char c = word.charAt(d); x.next[c - 'A'] = add(x.next[c - 'A'], word, d + 1); } return x; } // 判断字典中是否有该单词 private boolean contains(String word) { if (word == null) throw new java.lang.IllegalArgumentException("the word is null"); Node x = get(root, word, 0); if (x == null) return false; else return x.isWord; } // 以递归方式查找单词 // 当对应位置无字符时返回null,不然返回该字符节点 private Node get(Node node, String word, int d) { if (node == null) // 字典中该位置没有字符存储 return null; else { if (d < word.length()) { // 递归查找下一节点 char c = word.charAt(d); return get(node.next[c - 'A'], word, d + 1); } else return node; } } // 返回给定的BogGrand板中全部有效单词的集合,做为一个迭代。 public Iterable<String> getAllValidWords(BoggleBoard board) { if (board == null) throw new java.lang.IllegalArgumentException("the board is null"); // 减小内存 if (row != board.rows() || col != board.cols()) { row = board.rows(); // 行 col = board.cols(); // 列 marked = new boolean[row][col]; // 面板标志位 boardChar = new char[row][col]; // 面板字符位 computeAdj(); // 计算相邻位置的下标 } for (int i = 0; i < row; i++) // 行 for (int j = 0; j < col; j++) // 列 boardChar[i][j] = board.getLetter(i, j); // 拷贝字母 SET<String> words = DFS(); return words; } // 计算相邻位置的下标 private void computeAdj() { adjacents = new Adjacent[row * col]; // 相邻节点数组 for (int i = 0; i < row; i++) { // 行 for (int j = 0; j < col; j++) { // 列 int index = i * col + j; adjacents[index] = new Adjacent(); // adj[index].neineighbor[k]表示 临近节点的下标 if (i > 0) // 上 { // 左上 if (j > 0) adjacents[index].neighbor[adjacents[index].n++] = (i - 1) * col + j - 1; // 正上 adjacents[index].neighbor[adjacents[index].n++] = (i - 1) * col + j; // 右上 if (j < col -1) adjacents[index].neighbor[adjacents[index].n++] = (i - 1) * col + j + 1; } // 右 if (j < col -1) adjacents[index].neighbor[adjacents[index].n++] = i * col + j + 1; if (i < row -1) // 下 { // 右下 if (j < col -1) { adjacents[index].neighbor[adjacents[index].n++] = (i + 1) * col + j + 1; } // 正下 adjacents[index].neighbor[adjacents[index].n++] = (i + 1) * col + j; // 左下 if (j > 0) adjacents[index].neighbor[adjacents[index].n++] = (i + 1) * col + j - 1; } // 左 if (j > 0) adjacents[index].neighbor[adjacents[index].n++] = i * col + j - 1; } } } // 深度优先遍历搜索 private SET<String> DFS() { SET<String> words = new SET<>(); // 用于存放找到的单词 for (int i = 0; i < row; i++) for (int j = 0; j < col; j++) DFS(i, j, new StringBuilder(), words, root); return words; } // 深度优先搜索面板 private void DFS(int indexi, int indexj, StringBuilder pre, SET<String> words, Node node) { char c = boardChar[indexi][indexj]; Node next = node.next[c - 'A']; if (c == 'Q' && next != null) next = next.next['U' - 'A']; if (next == null) return; if (c == 'Q') // QU问题 pre.append("QU"); else pre.append(c); String string = pre.toString(); if (pre.length() > 2 && next.isWord) // 是单词 words.add(string); marked[indexi][indexj] = true; for (int i = 0; i < adjacents[indexi * col + indexj].n; i++) { int indexk = adjacents[indexi * col + indexj].neighbor[i]; //相邻节点的下标 int indexrow = indexk / col; // 该下标的节点所在行 int indexcol = indexk % col; // 该下标节点所在的列 if (!marked[indexrow][indexcol]) DFS(indexrow, indexcol, new StringBuilder(pre), words, next); } marked[indexi][indexj] = false; // 以便别的单词能继续查找 } // 若是它在字典中返回给定单词的分数,不然为零。 // (你能够假设这个词只包含大写字母A到Z)。 public int scoreOf(String word) { if (word == null) throw new java.lang.IllegalArgumentException("the word is null"); if (!contains(word)) return 0; if (word.length() <= 2) return 0; else if (word.length() <= 4) return 1; else if (word.length() == 5) return 2; else if (word.length() == 6) return 3; else if (word.length() == 7) return 5; else return 11; } public static void main(String[] args) { In in = new In(args[0]); String[] dictionary = in.readAllStrings(); BoggleSolver solver = new BoggleSolver(dictionary); BoggleBoard board = new BoggleBoard(args[1]); int score = 0; for (String word : solver.getAllValidWords(board)) { StdOut.println(word); score += solver.scoreOf(word); } StdOut.println("Score = " + score); } }