Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package com.datastructures.problems;
- import java.util.*;
- import java.util.stream.Stream;
- /**
- * Dictionary = [ CAT, DOG, BYTE, TUBE, CAN, ANT, CAR, TANK ]
- * Boggle = {
- * C J Z E
- * V A X B
- * X N T U
- * I A N K
- * }
- *
- * Dictionary = [ APPLE, PICKLE, SIDE, KICK, SICK, MOOD, CAT, CATS, MAN, SUPER, ANTMAN, GODZILLA,
- * DOG, DOT, SINE, COS, SIGNAL, BITCOIN, COOL, ZAPPER ]
- *
- * Boggle = {
- * C N T S S
- * D A T I N
- * O O M E L
- * S I K N D
- * P I C L E
- * }
- *
- * Approach:
- * Solve it using Graph (DFS) and Trie
- */
- public class BoggleGameSolver {
- private static int[][] DELTAS = new int[][] {
- { -1, -1 },
- { -1, 1 },
- { 1, 1 },
- { 1, -1 },
- { 1, 0 },
- { 0, 1 },
- { -1, 0 },
- { 0, -1 },
- };
- public static void main(String[] args) {
- String[] dict = new String[] { "CAT", "DOG", "BYTE", "TUBE", "CAN", "ANT", "CAR", "TANK" };
- char[][] boggle = new char[][] {
- { 'C', 'J', 'Z', 'E' },
- { 'V', 'A', 'X', 'B' },
- { 'X', 'N', 'T', 'U' },
- { 'I', 'A', 'N', 'K' }
- };
- solveBoggle(dict, boggle, 4, 4);
- }
- /**
- *
- * @param dict - dictionary of words
- * @param boggle - matrix of m x n
- * @param m - rows
- * @param n - columns
- * @return
- */
- private static void solveBoggle(String[] dict, char[][] boggle, int m, int n) {
- Trie trie = new Trie(dict);
- Set<String> results = new HashSet<>();
- for(int i=0; i<m; i++) {
- for(int j=0; j<n; j++) {
- StringBuilder w = new StringBuilder();
- w.append(boggle[i][j]);
- solveBoggleHelper(new Cell(i, j), w, boggle, new HashSet<>(), results, trie, m, n);
- w.deleteCharAt(w.length()-1);
- }
- }
- System.out.println("Found words: " + results);
- }
- private static void solveBoggleHelper(Cell cell, StringBuilder w, char[][] boggle, Set<Cell> visited, Set<String> results, Trie trie, int maxRows, int maxCols) {
- visited.add(cell);
- Trie.Node node = trie.searchNode(w.toString());
- if(node != null) {
- if(node.leaf) {
- results.add(w.toString());
- }
- List<Cell> neighbours = getNeighbours(cell, visited, maxRows, maxCols);
- if(neighbours != null) {
- for(Cell c: neighbours) {
- w.append(boggle[c.r][c.c]);
- solveBoggleHelper(c, w, boggle, new HashSet<>(), results, trie, maxRows, maxCols);
- w.deleteCharAt(w.length()-1);
- }
- }
- }
- }
- private static List<Cell> getNeighbours(Cell cell, Set<Cell> visited, int maxRows, int maxCols) {
- List<Cell> cells = new ArrayList<>();
- for(int i = 0; i< DELTAS.length; i++) {
- Cell nextCell = new Cell(cell.r + DELTAS[i][0], cell.c + DELTAS[i][1]);
- if(valid(nextCell, maxRows, maxCols) && !visited.contains(nextCell)) {
- cells.add(nextCell);
- }
- }
- return cells;
- }
- private static boolean valid(Cell cell, int maxRow, int maxCol) {
- return cell.r >= 0 && cell.r < maxRow && cell.c >= 0 && cell.c < maxCol;
- }
- private static class Cell {
- private int r;
- private int c;
- public Cell(int r, int c) {
- this.r = r;
- this.c = c;
- }
- @Override
- public boolean equals(Object o) {
- if (this == o) return true;
- if (o == null || getClass() != o.getClass()) return false;
- Cell cell = (Cell) o;
- return r == cell.r &&
- c == cell.c;
- }
- @Override
- public int hashCode() {
- return Objects.hash(r, c);
- }
- @Override
- public String toString() {
- return String.format("[%s, %s]", r, c);
- }
- }
- private static class Trie {
- private Node root;
- public Trie() {
- root = new Node(' ');
- }
- public Trie(String[] words) {
- this();
- build(words);
- }
- @Override
- public String toString() {
- return String.format("[%s]", root);
- }
- public void build(String[] words) {
- Stream.of(words).forEach(w -> add(w));
- }
- public boolean containsWord(String w) {
- Node node = searchNode(w);
- return node != null && node.leaf;
- }
- private Node searchNode(String w) {
- if(root.children == null) return null;
- Node node = root;
- for(int i=0; i<w.length(); i++) {
- char ch = w.charAt(i);
- int j = ch - 'A';
- if(node.children == null || node.children[j] == null) return null;
- node = node.children[j];
- }
- return node;
- }
- public void add(String w) {
- Node node = root;
- for(int i=0; i<w.length(); i++) {
- char ch = w.charAt(i);
- node = add(node, ch, i == w.length()-1);
- }
- }
- private Node add(Node node, char ch, boolean leaf) {
- if(node.children == null) node.children = new Node[26];
- int i = ch - 'A';
- if(node.children[i] == null) {
- Node newNode = new Node(ch, leaf);
- node.children[i] = newNode;
- return newNode;
- } else {
- node.children[i].leaf = leaf;
- return node.children[i];
- }
- }
- private static class Node {
- private char ch;
- private boolean leaf;
- private Node[] children;
- public Node(char ch) {
- this.ch = ch;
- }
- public Node(char ch, boolean leaf) {
- this.ch = ch;
- this.leaf = leaf;
- }
- @Override
- public String toString() {
- return String.format("[%s, %s, %s]", ch, leaf, Arrays.toString(children));
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement