1. 問題描述

princeton_algs4第四周的編程作業(yè)Boggle论寨，一個(gè)拼字游戲。將棋盤上的字母按照限定的順序連接爽茴，如果得到給定字典中出現(xiàn)的單詞葬凳，則記分。

游戲說明

• 一個(gè)字母只能夠與它的上室奏、下火焰、左、右胧沫、左上昌简、右上、左下绒怨、右下8個(gè)方向上的字母相連纯赎。
• 單詞中同一個(gè)位置的字母只能出現(xiàn)一次。
• 單詞至少有三個(gè)字母南蹂。
• 單詞必須存在于給定的字典中犬金。

我們要完成的任務(wù)就是：已知一個(gè)字典和一個(gè)棋盤(棋盤上每個(gè)位置的字母可以得到)，找出該棋盤上的字母可以組成的所有合法單詞六剥。

2. 解決思路

2.1 對(duì)棋盤建模

我們考慮如何在棋盤上搜索單詞晚顷。既然每個(gè)單詞是沿著棋盤上的字母與其臨接的字母一個(gè)一個(gè)串起來(lái)的，那么我們可以把棋盤看成圖疗疟，棋盤上各位置的字母可以看成圖中的結(jié)點(diǎn)该默，從一個(gè)字母與其能達(dá)到的另一個(gè)字母之間建立一條邊，假設(shè)一個(gè)4*4大小的棋盤可以構(gòu)成如下的無(wú)向圖秃嗜。

根據(jù)棋盤構(gòu)成的圖

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 改造深度優(yōu)先搜索

接下來(lái)我們可以使用深度優(yōu)先的方法在圖中搜索所有的合法單詞必指。首先判斷是否出現(xiàn)了合法單詞：當(dāng)前字符串長(zhǎng)度大于2，并且存在于與字典中恕洲。如果是合法單詞塔橡，就記錄下來(lái)并且繼續(xù)搜索梅割。這里有一個(gè)限制條件要注意：就是同一個(gè)位置的字母不能兩次出現(xiàn)在得到的字符串中。如果我們使用一般DFS中用一個(gè)boolean型數(shù)組marked[]來(lái)標(biāo)記當(dāng)前所遍歷到的結(jié)點(diǎn)時(shí)就會(huì)出現(xiàn)一個(gè)問題：原本marked標(biāo)記的是所有遍歷過的結(jié)點(diǎn)葛家，如果某個(gè)結(jié)點(diǎn)已經(jīng)遍歷過了户辞，則下次遍歷到它時(shí)就會(huì)跳過。而我們這里的需求是正在遍歷的結(jié)點(diǎn)們中不能重復(fù)出現(xiàn)同一個(gè)位置的結(jié)點(diǎn)癞谒。舉個(gè)例子：假如說 PINES 和 PIDS 都是合法的單詞底燎。我們沿著P----I----N----E----S一路遍歷下來(lái)，得到了PINES這個(gè)合法單詞弹砚，這些正在被遍歷的點(diǎn)都應(yīng)該被標(biāo)記双仍，當(dāng)我們繼續(xù)遍歷到P——I——D時(shí)，之前遍歷過的N桌吃，E朱沃，S結(jié)點(diǎn)這時(shí)候應(yīng)該被取消標(biāo)記，不然我們就遍歷不到S結(jié)點(diǎn)茅诱，就無(wú)法找出合法的單詞PIDS了逗物。改造后的marked[]與之前的區(qū)別就是，之前marked就是負(fù)責(zé)把所有遍歷過的點(diǎn)標(biāo)記出來(lái)瑟俭，而現(xiàn)在我們只標(biāo)記所有存在于當(dāng)前搜索出的路徑上的結(jié)點(diǎn)敬察，一旦某個(gè)節(jié)點(diǎn)不在當(dāng)前遍歷的路徑上時(shí)，則立即取消標(biāo)記尔当。于是我的做法是除了之前的數(shù)組marked[]莲祸，新加了一個(gè)數(shù)據(jù)Stack<Integer> visitingDices用來(lái)記錄當(dāng)前路徑遍歷到的結(jié)點(diǎn)。一旦完成某個(gè)結(jié)點(diǎn)的遍歷椭迎，則立刻從棧頂彈出該結(jié)點(diǎn)锐帜，并取消相應(yīng)標(biāo)記。

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 對(duì)字典建模

最后還有一個(gè)大問題要解決：如何快速地在字典中查找一個(gè)單詞是否存在與該字典中畜号。由于這周主要講的數(shù)據(jù)結(jié)構(gòu)是前綴樹Trie,所以毫無(wú)疑問缴阎，我們應(yīng)該將字典存儲(chǔ)在Trie中。其實(shí)也可以這樣理解：我們用給定的字典構(gòu)建出一棵前綴樹（也叫字典樹）后简软，棋盤上以某個(gè)字母為起點(diǎn)用DFS遍歷到的字母順序蛮拔，就是在字典樹中前進(jìn)的方向，如果前進(jìn)到某個(gè)結(jié)點(diǎn)為空痹升，則說明在字典中不存在以DFS遍歷到的字符串為前綴的單詞建炫，因此對(duì)于棋盤來(lái)說也就沒有必要在當(dāng)前結(jié)點(diǎn)繼續(xù)用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. 代碼

查看完整代碼戳這里