Class BoggleSolver

LabEnv/09Lab/BoggleSolver.java:12–124

import java.util.HashSet;

public class BoggleSolver {
    private static class Node {
        private boolean isTernimal = false;
        private Node[] children = new Node[26];
    }

    private final Node root; // should not be modified
    private final int[][] dirs = {
            { -1, -1 }, { -1, 0 }, { -1, 1 },
            { 0, 1 }, { 0, -1 },
            { 1, 1 }, { 1, 0 }, { 1, -1 }
    };

    // Initializes the data structure using the given array of strings as the dictionary.
    // (You can assume each word in the dictionary contains only the uppercase letters A through Z.)
    public BoggleSolver(String[] dictionary) {
        root = new Node();
        for (String s : dictionary)
            put(root, s);
    }

    private void put(Node x, String key) {
        for (char c : key.toCharArray()) {
            if (x.children[c - 'A'] == null)
                x.children[c - 'A'] = new Node();
            x = x.children[c - 'A'];
        }
        x.isTernimal = true;
    }

    private boolean get(Node x, String key) {
        for (char c : key.toCharArray()) {
            x = x.children[c - 'A'];
            if (x == null) return false;
        }
        return x.isTernimal;
    }

    // Returns the set of all valid words in the given Boggle board, as an Iterable.
    public Iterable<String> getAllValidWords(BoggleBoard board) {
        HashSet<String> set = new HashSet<>();
        boolean[][] visited = new boolean[board.rows()][board.cols()];
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < board.rows(); ++i) {
            for (int j = 0; j < board.cols(); ++j) {
                dfs(root, board, i, j, sb, visited, set);
            }
        }

        return set;
    }

    private void dfs(Node x, BoggleBoard board, int i, int j, StringBuilder sb, boolean[][] visited,
                     HashSet<String> set) {
        char c = board.getLetter(i, j);
        Node next = x.children[c - 'A'];
        if (next == null) return;