首页 > itarticle > [java]r-way trie&dfs(boggle game) 26-way Trie

[java]r-way trie&dfs(boggle game) 26-way Trie

admin 11月 12, 2020 0

This is the forth assignment of Algorithms II-Princeton-Coursera

This program is a word game called Boggle. Players use a 16 cubic dice board to build valid words.

This program is to creat a R-way Trie dictionary to store a dicionary and check prefix, and to creat a DFS to look through all words.

I struggled for a long time in the DFS recursive part. It doesn’t like what I learned, finding the way to a vertice(using one graph). This program need to use different graph, and solution is in line 73.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
 
import java.util.ArrayList;
import java.util.List;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
 * This algorithm is to implement R-way tries set to store a dictionary and to check prefix
 * Deep First Search to make up strings.
 * @author Daihu
 * @date   2017年2月22日
 */
public class  {
    
    private int row, col;
    private TrieSET dic;
    public (String[] dictionary) {
        dic = new TrieSET();
        for (String word: dictionary) {
            dic.add(word);
        }
    }
    
     * @param board
     * @return the set of all valid words in the given board
     */
    public Iterable<String> getAllValidWords(BoggleBoard board) {
        List<String> container = new ArrayList<>();
        boolean[][] marked;
        row = board.rows();
        col = board.cols();
        
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                String str = "";
                marked = new boolean[row][col];
                dfs(i, j, board, str, marked, container);
            }
        }
        return container;
    }
    
     * DFS: recursively add char into string to check if in dictionary
     * true for storing in container
     * 
     * @param i, j: the position of the the begin char
     * @param board
     * @param str: store in container if this string is in dictionary
     * @param marked: mark for checking if visited
     * @param container: the result containing strings in dictionary
     */
    private void dfs(int i, int j, BoggleBoard board, String str, boolean[][] marked, List<String> container) {
        char letter;
        if (i >= 0 && i < row && j >= 0 && j < col && !marked[i][j]) {
            letter = board.getLetter(i, j);
            if (letter == 'Q') 
                str += "QU";
            else 
                str += letter;
            if (str.length() > 2 && dic.contains(str) && !container.contains(str))
                container.add(str);
            if (!dic.isPrefix(str)) return;
            marked[i][j] = true;
            dfs(i+1, j, board, str, marked, container);
            dfs(i-1, j, board, str, marked, container);
            dfs(i, j+1, board, str, marked, container);
            dfs(i, j-1, board, str, marked, container);
            dfs(i+1, j+1, board, str, marked, container);
            dfs(i-1, j-1, board, str, marked, container);
            dfs(i+1, j-1, board, str, marked, container);
            dfs(i-1, j+1, board, str, marked, container);
            marked[i][j] = false;
        }
    }
    
    
     * @param word: a string word
     * @return: the score of the word
     */
    public int scoreOf(String word) {
        if (!dic.contains(word))
            return 0;
        int len = word.length();
        switch(len) {
            case 0:
            case 1:
            case 2: return 0;
            case 3: return 1;
            case 4: return 1;
            case 5: return 2;
            case 6: return 3;
            case 7: return 5;
            default: 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);
    }
}

26-way Trie

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
 * 26-way trie node
 * 
 * This class is for storing dictionary.
 * It bases on the provided TrieSET, which is 256-way and without 
 * isPrefix() function
 * 
 * 26-way for memory optimization
 * isPrefix() for timing optimization
 * 
 * @author Daihu
 * @date   2017-2-22
 */
public class TrieSET {
    private static final int R = 26;
    private Node root;
    private boolean findPrefix;
    // 26-way trie node
    private static class Node {
        private Node[] next = new Node[R];
        private boolean isString;
    }
    public TrieSET() {
    }
    
    public boolean contains(String key) {
        Node x = get(root, key, 0);
        if (x == null) return false;
        return x.isString;
    }
    private Node get(Node x, String key, int d) {
        if (x == null) return null;
        if (d == key.length()) return x;
        char c = key.charAt(d);
        return get(x.next[c-65], key, d+1);
    }
    public void add(String key) {
        root = add(root, key, 0);
    }
    private Node add(Node x, String key, int d) {
        if (x == null) x = new Node();
        if (d == key.length()) {
            x.isString = true;
        }
        else {
            char c = key.charAt(d);
            x.next[c-65] = add(x.next[c-65], key, d+1);
        }
        return x;
    }
    
     * This function is for optimization. If a string is not prefix of words
     * in dictionary, we don't need to go on
     * @param prefix
     * @return if the string is the prefix of words in dictionary
     */
    public boolean isPrefix(String prefix) {
        findPrefix = false;
        Node x = get(root, prefix, 0);
        collect(x, new StringBuilder(prefix));
        return findPrefix;
    }
    private void collect(Node x, StringBuilder prefix) {
        if (findPrefix) return;
        if (x == null) return;
        if (x.isString) findPrefix = true;
        for (char c = 0; c < R; c++) {
            prefix.append(c);
            collect(x.next[c], prefix);
            prefix.deleteCharAt(prefix.length() - 1);
        }
    }
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能