package Misc;

import java.util.*;

public class WordBoggle {

/**

* O(nm * 8^s + ws) time where n = width of boggle board, m = height of boggle board, s = length of

* longest word in string array, w = length of string array, 8 is due to 8 explorable neighbours

* O(nm + ws) space.

*/

public static List<String> boggleBoard(char[][] board, String[] words) {

Trie trie = new Trie();

for (String word : words) trie.add(word);

Set<String> finalWords = new HashSet<>();

boolean[][] visited = new boolean[board.length][board.length];

for (int i = 0; i < board.length; i++)

for (int j = 0; j < board[i].length; j++)

explore(i, j, board, trie.root, visited, finalWords);

return new ArrayList<>(finalWords);

}

public static void main(String[] args) {

// Testcase

List<String> ans =

new ArrayList<>(

Arrays.asList("a", "boggle", "this", "NOTRE_PEATED", "is", "simple", "board"));

assert (boggleBoard(

new char[][] {

{'t', 'h', 'i', 's', 'i', 's', 'a'},

{'s', 'i', 'm', 'p', 'l', 'e', 'x'},

{'b', 'x', 'x', 'x', 'x', 'e', 'b'},

{'x', 'o', 'g', 'g', 'l', 'x', 'o'},

{'x', 'x', 'x', 'D', 'T', 'r', 'a'},

{'R', 'E', 'P', 'E', 'A', 'd', 'x'},

{'x', 'x', 'x', 'x', 'x', 'x', 'x'},

{'N', 'O', 'T', 'R', 'E', '_', 'P'},

{'x', 'x', 'D', 'E', 'T', 'A', 'E'},

},

new String[] {

"this",

"is",

"not",

"a",

"simple",

"test",

"boggle",

"board",

"REPEATED",

"NOTRE_PEATED",

})

.equals(ans));

}

public static void explore(

int i,

int j,

char[][] board,

TrieNode trieNode,

boolean[][] visited,

Set<String> finalWords) {

if (visited[i][j]) return;

char letter = board[i][j];

if (!trieNode.children.containsKey(letter)) {

return;

}

visited[i][j] = true;

trieNode = trieNode.children.get(letter);

if (trieNode.children.containsKey('*')) finalWords.add(trieNode.word);

List<Integer[]> neighbors = getNeighbors(i, j, board);

for (Integer[] neighbor : neighbors)

explore(neighbor[0], neighbor[1], board, trieNode, visited, finalWords);

visited[i][j] = false;

}

public static List<Integer[]> getNeighbors(int i, int j, char[][] board) {

List<Integer[]> neighbors = new ArrayList<>();

if (i > 0 && j > 0) neighbors.add(new Integer[] {i - 1, j - 1});

if (i > 0 && j < board[0].length - 1) neighbors.add(new Integer[] {i - 1, j + 1});

if (i < board.length - 1 && j < board[0].length - 1)

neighbors.add(new Integer[] {i + 1, j + 1});

if (i < board.length - 1 && j > 0) neighbors.add(new Integer[] {i + 1, j - 1});

if (i > 0) neighbors.add(new Integer[] {i - 1, j});

if (i < board.length - 1) neighbors.add(new Integer[] {i + 1, j});

if (j > 0) neighbors.add(new Integer[] {i, j - 1});

if (j < board[0].length - 1) neighbors.add(new Integer[] {i, j + 1});

return neighbors;

}

}

// Trie used to optimize string search

class TrieNode {

Map<Character, TrieNode> children = new HashMap<>();

String word = "";

}

class Trie {

TrieNode root;

char endSymbol;

public Trie() {

this.root = new TrieNode();

this.endSymbol = '*';

}

public void add(String str) {

TrieNode node = this.root;

for (int i = 0; i < str.length(); i++) {

char letter = str.charAt(i);

if (!node.children.containsKey(letter)) {

TrieNode newNode = new TrieNode();

node.children.put(letter, newNode);

}

node = node.children.get(letter);

}

node.children.put(this.endSymbol, null);

node.word = str;

}

}