Coursera 算法二 week 4 Boggle

lxc1910 2021-08-30 原文

这次的作业主要用到了单词查找树和深度优先搜索。

1.在深度优先搜索中，在当前层的递归调用前，将marked数组标记为true。当递归调用返回到当前层时，应将marked数组标记为false。这样既可以使访问完当前节点之后不会访问到达当前节点路径上的节点，又可以从其它路径上访问到该节点。

2.当词典中没有单词以到达当前节点后的字符串为前缀时，即可停止深度优先搜索。

3.重写单词查找树，R为26，避免消耗过多的空间。另外keysWithPrefix函数改为hasKeysWithPrefix函数，因为不需要查找以某一字符串为前缀的所有单词，而只需判断是否有以某一字符串为前缀的单词。

 1 import java.util.HashSet;
 2 import java.util.Set;
 3 
 4 public class BoggleSolver
 5 {
 6     private TrieSET2 dictionary = new TrieSET2();
 7     
 8     public BoggleSolver(String[] dictionary)
 9     {
10         for (String s : dictionary)
11             this.dictionary.put(s);
12     }
13     private int m, n;
14     public Iterable<String> getAllValidWords(BoggleBoard board)
15     {
16         Set<String> set = new HashSet<String>();
17         m = board.rows();
18         n = board.cols();
19         for (int i = 0; i < m; i++)
20         {
21             for (int j = 0; j < n; j++)
22             {
23                 marked = new boolean[m][n];
24                 dfs (set, board, i, j, "");
25             }
26         }
27         return set;
28     }
29     private boolean[][] marked;
30     private boolean isMarked(int i, int j)
31     {
32         if (i < 0 || i >= m || j < 0 || j >= n)
33             return true;
34         return marked[i][j];
35     }
36     private void dfs(Set<String> set, BoggleBoard board, int i, int j, String s)
37     {
38         char c = board.getLetter(i, j);
39         if (c == \'Q\') s += "QU";
40         else s += c;
41         if (!dictionary.hasKeysWithPrefix(s)) return;
42         marked[i][j] = true;
43         if (s.length() > 2 && dictionary.contains(s))
44             set.add(s);
45         for (int k = -1; k < 2; k++)
46         {
47             for (int l = -1; l < 2; l++)
48             {
49                 if (!isMarked(i + k, j + l))
50                     dfs(set, board, i + k, j + l, s);
51             }
52         }
53         marked[i][j] = false;
54     }
55     
56     public int scoreOf(String word)
57     {
58         if (!dictionary.contains(word))
59             return 0;
60         int length = word.length();
61         if (length < 3) return 0;
62         else if (length < 5) return 1;
63         else if (length == 5) return 2;
64         else if (length == 6) return 3;
65         else if (length == 7) return 5;
66         else return 11;
67     }
68 }

 1 import edu.princeton.cs.algs4.Queue;
 2 
 3 public class TrieSET2
 4 {
 5     private static int R = 26;
 6     private Node root;
 7     
 8     private static class Node
 9     {
10         private boolean hasWord;
11         private Node[] next = new Node[R];
12     }
13     
14     public void put(String key)
15     {
16         root = put(root, key, 0);
17     }
18     
19     private int charAt(String s, int d)
20     {
21         return s.charAt(d) - \'A\';
22     }
23     
24     private Node put(Node x, String key, int d)
25     {
26         if (x == null) x = new Node();
27         if (d == key.length())
28         {
29             x.hasWord = true;
30             return x;
31         }
32         int c = charAt(key, d);
33         x.next[c] = put(x.next[c], key, d+1);
34         return x;
35     }
36     
37     public boolean contains(String key)
38     {
39         Node x = get(root, key, 0);
40         if (x == null) return false;
41         return x.hasWord;
42     }
43     
44     private Node get(Node x, String key, int d)
45     {
46         if (x == null) return null;
47         if (d == key.length()) return x;
48         int c = charAt(key, d);
49         return get(x.next[c], key, d+1);
50     }
51     
52     public boolean hasKeysWithPrefix(String pre)
53     {
54         return get(root, pre, 0) != null;
55     }
56 }