1. 问题描述

princeton_algs4第四周的编程作业Boggle，一个拼字游戏。将棋盘上的字母按照限定的顺序连接，如果得到给定字典中出现的单词，则记分。

游戏说明

• 一个字母只能够与它的上、下、左、右、左上、右上、左下、右下8个方向上的字母相连。
• 单词中同一个位置的字母只能出现一次。
• 单词至少有三个字母。
• 单词必须存在于给定的字典中。

我们要完成的任务就是：已知一个字典和一个棋盘(棋盘上每个位置的字母可以得到)，找出该棋盘上的字母可以组成的所有合法单词。

2. 解决思路

2.1 对棋盘建模

我们考虑如何在棋盘上搜索单词。既然每个单词是沿着棋盘上的字母与其临接的字母一个一个串起来的，那么我们可以把棋盘看成图，棋盘上各位置的字母可以看成图中的结点，从一个字母与其能达到的另一个字母之间建立一条边，假设一个4*4大小的棋盘可以构成如下的无向图。

根据棋盘构成的图

rows = board.rows();
cols = board.cols();
adj = (Bag<Integer>[]) new Bag[rows*cols];  
        
for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
        int v = i*cols + j;
        adj[v] = new Bag<Integer>();
        if (checkWIsValid(i-1, j)) adj[v].add((i-1) * cols + j);
        if (checkWIsValid(i+1, j)) adj[v].add((i+1) * cols + j);
        if (checkWIsValid(i, j+1)) adj[v].add(i * cols + j+1);
        if (checkWIsValid(i, j-1)) adj[v].add(i * cols + j-1);
        if (checkWIsValid(i+1, j-1)) adj[v].add((i+1) * cols + j-1);
        if (checkWIsValid(i+1, j+1)) adj[v].add((i+1) * cols + j+1);
        if (checkWIsValid(i-1, j-1)) adj[v].add((i-1) * cols + j-1);
        if (checkWIsValid(i-1, j+1)) adj[v].add((i-1) * cols + j+1);
    }
}

2.2 改造深度优先搜索

接下来我们可以使用深度优先的方法在图中搜索所有的合法单词。首先判断是否出现了合法单词：当前字符串长度大于2，并且存在于与字典中。如果是合法单词，就记录下来并且继续搜索。这里有一个限制条件要注意：就是同一个位置的字母不能两次出现在得到的字符串中。如果我们使用一般DFS中用一个boolean型数组marked[]来标记当前所遍历到的结点时就会出现一个问题：原本marked标记的是所有遍历过的结点，如果某个结点已经遍历过了，则下次遍历到它时就会跳过。而我们这里的需求是正在遍历的结点们中不能重复出现同一个位置的结点。举个例子：假如说 PINES 和 PIDS 都是合法的单词。我们沿着P----I----N----E----S一路遍历下来，得到了PINES这个合法单词，这些正在被遍历的点都应该被标记，当我们继续遍历到P——I——D时，之前遍历过的N，E，S结点这时候应该被取消标记，不然我们就遍历不到S结点，就无法找出合法的单词PIDS了。改造后的marked[]与之前的区别就是，之前marked就是负责把所有遍历过的点标记出来，而现在我们只标记所有存在于当前搜索出的路径上的结点，一旦某个节点不在当前遍历的路径上时，则立即取消标记。于是我的做法是除了之前的数组marked[]，新加了一个数据Stack<Integer> visitingDices用来记录当前路径遍历到的结点。一旦完成某个结点的遍历，则立刻从栈顶弹出该结点，并取消相应标记。

private void searchValidWords(int v, Node x, String str, Stack<Integer> visitingDices) {
    if (str.length() > 2 && x != null && x.val == 1) {
        validWords.add(str);
    }   
    for (int w : adj[v]) {  
        char c = getLetterOnBoard(w);
        if (!marked[w] && x != null && x.next[c -'A'] != null) {
            visitingDices.push(w);
            marked[w] = true;
            if (c == 'Q') { 
                searchValidWords(w, x.next['Q'-'A'].next['U' - 'A'], str+"QU", visitingDices);
            }                   
            else {
                searchValidWords(w, x.next[c -'A'], str+c, visitingDices);
            }
            int index = visitingDices.pop();
            marked[index] = false;          
        } 
    }
}

2.3 对字典建模

最后还有一个大问题要解决：如何快速地在字典中查找一个单词是否存在与该字典中。由于这周主要讲的数据结构是前缀树Trie,所以毫无疑问，我们应该将字典存储在Trie中。其实也可以这样理解：我们用给定的字典构建出一棵前缀树（也叫字典树）后，棋盘上以某个字母为起点用DFS遍历到的字母顺序，就是在字典树中前进的方向，如果前进到某个结点为空，则说明在字典中不存在以DFS遍历到的字符串为前缀的单词，因此对于棋盘来说也就没有必要在当前结点继续用DFS搜索下去了。

在字典树的查找

public BoggleSolver(String[] dictionary) {
    root = new Node();
    for (int i = 0; i < dictionary.length; i++) {
        put(dictionary[i]);
    }
}
    
private static class Node {
    private int val = 0;
    private Node[] next = new Node[26];
}
    
private int get(String key) {
    Node x = get(root, key, 0);
    if (x == null) return 0;
    return x.val;
}
        
private Node get(Node x, String key, int d) {
    if (x == null) return null;
    if (d == key.length()) return x;
    int c = key.charAt(d) - 'A';
    return get(x.next[c], key, d+1);
        }
    
        private void put(String key) {
            root = put(root, key, 0);
}
    
private Node put(Node x, String key, int d) {
    if (x == null) x = new Node();
    if (d == key.length()) {
        x.val = 1;
            return x;
        }
        int c = key.charAt(d) - 'A';
        x.next[c] = put(x.next[c], key, d+1);
        return x;
    }

3. 代码

查看完整代码戳这里