Boggle Board

Category: Graphs

```

Problem Statement

Sample Input board = [ ["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"], ], words = [ "this", "is", "not", "a", "simple", "boggle", "board", "test", "REPEATED", "NOTRE-PEATED", ] Sample Output ["this", "is", "a", "simple", "boggle", "board", "NOTRE-PEATED"] Hints Hint 1 You can divide this question into two separate problems: one part involves traversing the boggle board in such a way that allows you to construct strings letter by letter; the other part involves actually comparing the strings you construct in the board against the words in the list that you're given. For the second part, what data structure lends itself very well to matching characters to multiple strings at once? Hint 2 Try creating a trie out of the input list of words. This will allow you to compare letters in the boggle board against all input words in constant time. How can you eciently traverse the boggle board to construct all potentially valid strings, without counting letters twice in any string? Hint 3 Treat the board as a graph, where each element in the board is a node with up to 8 neighboring nodes. Traverse it in a depth-rst-search-like fashion, checking if letters are contained in the trie and traversing the trie simultaneously if it makes sense to do so. How can you keep track of letters that you've already visited in order to avoid erroneously counting some of them twice in a single string? Could you keep track of visited nodes in an auxiliary data structure? Hint 4 Keeping in mind that you only want to mark nodes as visited in a single branch of the graph that you're traversing (i.e., you don't want the state of visited nodes in one branch of the graph to spill into the state of another branch of the graph), try marking any node you traverse as unvisited at the end of the recursive call that actually traverses it, after traversing through all of the node's neighbors and performing the same actions on them recursively. Optimal Space & Time Complexity O(nm*8^s + ws) time | O(nm + ws) space - where n is the width the board, m is the height of the board, w is the number of words, and s is the length of the longest word

```

Approach & Solution

Solution 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; } static class TrieNode { Map children = new HashMap(); Map children = new HashMap(); String word = ""; } static 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; } } }

Solution 2

```java import java.util.; 4 class Program { // O(nm8^s + ws) time | O(nm + ws) space public static List boggleBoard(char[][] board, String[] words) { Trie trie = new Trie(); for (String word : words) { trie.add(word); } Set finalWords = new HashSet(); boolean[][] visited = new boolean[board.length][board[0].length]; for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { explore(i, j, board, trie.root, visited, finalWords); } } List finalWordsArray = new ArrayList(); finalWordsArray.addAll(finalWords); return finalWordsArray; } 23 public static void explore( int i, int j, char[][] board, TrieNode trieNode, boolean[][] visited, Set 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 neighbors = getNeighbors(i, j, board); for (Integer[] neighbor : neighbors) { explore(neighbor[0], neighbor[1], board, trieNode, visited, finalWords);

```

Test Cases

``` Test Case 1 { "board": [ ["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"] ], "words": [ "this", "is", "not", "a", "simple", "boggle", "board", "test", "REPEATED", "NOTRE-PEATED" ] } Test Case 2 { "board": [ ["y", "g", "f", "y", "e", "i"], ["c", "o", "r", "p", "o", "u"], ["j", "u", "z", "s", "e", "l"], ["s", "y", "u", "r", "h", "p"], ["e", "a", "e", "g", "n", "d"], ["h", "e", "l", "s", "a", "t"] ], "words": [ "san", "sana", "at", "vomit", "yours", "help", "end", "been", "bed", "danger", "calm", "ok", "chaos", "complete", "rear", "going", "storm", "face", "epual", "dangerous" ] } Test Case 3 { "board": [ ["a", "b", "c", "d", "e"], ["f", "g", "h", "i", "j"], ["k", "l", "m", "n", "o"], ["p", "q", "r", "s", "t"], ["u", "v", "w", "x", "y"] ], "words": ["agmsy", "agmsytojed", "agmsytojedinhcbgl", "agmsytojedinhcbfl"] } Test Case 4 { "board": [["a", "b"], ["c", "d"]], "words": ["abcd", "abdc", "acbd", "acdb", "adbc", "adcb", "abca"] } Test Case 5 { "board": [ ["f", "t", "r", "o", "p", "i", "k", "b", "o"], ["r", "w", "l", "p", "e", "u", "e", "a", "b"], ["j", "o", "t", "s", "e", "l", "f", "l", "p"], ["s", "z", "u", "t", "h", "u", "o", "p", "i"], ["k", "a", "e", "g", "n", "d", "r", "g", "a"], ["h", "n", "l", "s", "a", "t", "e", "t", "x"] ], "words": [ "frozen", "rotten", "teleport", "city", "zutgatz", "kappa", "before", "rope", "obligate", "annoying" ] } Test Case 6 { "board": [ ["c", "o", "m"], ["r", "p", "l"], ["c", "i", "t"], ["o", "a", "e"], ["f", "o", "d"], ["z", "r", "b"], ["g", "i", "a"], ["o", "a", "g"], ["f", "s", "z"], ["t", "e", "i"], ["t", "w", "d"] ], "words": [ "commerce", "complicated", "twisted", "zigzag", "comma", "foobar", "baz", "there" ] } Test Case 7 { "board": [ ["c", "o", "m"], ["r", "p", "l"], ["c", "i", "t"], ["o", "a", "e"], ["f", "o", "d"], ["z", "r", "b"], ["g", "i", "a"], ["o", "a", "g"], ["f", "s", "z"], ["t", "e", "i"], ["t", "w", "d"] ], "words": [ "cr", "oc", "ml", "iao", "opo", "zrb", "big", "fs", "ogiagao", "dwd", "twt" ] } Test Case 8 { "board": [ ["c", "o", "m"], ["r", "p", "l"], ["c", "i", "t"], ["o", "a", "e"], ["f", "o", "d"], ["z", "r", "b"], ["g", "i", "a"], ["o", "a", "g"], ["f", "s", "z"], ["t", "e", "i"], ["t", "w", "d"] ], "words": [ "comlpriteacoofziraagsizefttw", "comlpriteacoofzirabagsizefottw", "comlpriteacoofziraagsizefottw", "comlpriteacoofzirabagsizeftttw" ] }