Backtracking + Trie

\n

\n\nIntuitively, start from every cell and try to build a word in the dictionary. `Backtracking (dfs)` is the powerful way to exhaust every possible ways. Apparently, we need to do `pruning` when current character is not in any word. \n\n1. How do we instantly know the current character is invalid? `HashMap`? \n2. How do we instantly know what\'s the next valid character? `LinkedList`?\n3. But the next character can be chosen from a list of characters. `"Mutil-LinkedList"`?\n\nCombing them, `Trie` is the natural choice. Notice that:\n\n1. `TrieNode` is all we need. `search` and `startsWith` are useless.\n2. No need to store character at TrieNode. `c.next[i] != null` is enough.\n3. Never use `c1 + c2 + c3`. Use `StringBuilder`.\n4. No need to use `O(n^2)` extra space `visited[m][n].` \n5. No need to use `StringBuilder`. Storing `word` itself at leaf node is enough.\n6. No need to use `HashSet` to de-duplicate. Use "one time search" trie.\n\nFor more explanations, check out [dietpepsi\'s blog][1].\n\n

\n

Code Optimization

\n

\n\nUPDATE: Thanks to @dietpepsi we further improved from `17ms` to `15ms`.\n\n1. `59ms`: Use `search` and `startsWith` in Trie class like [this popular solution.][2]\n2. `33ms`: Remove Trie class which unnecessarily starts from `root` in every `dfs` call. \n3. `30ms`: Use `w.toCharArray()` instead of `w.charAt(i)`.\n4. `22ms`: Use `StringBuilder` instead of `c1 + c2 + c3`.\n5. `20ms`: Remove `StringBuilder` completely by storing `word` instead of `boolean` in TrieNode.\n6. `20ms`: Remove `visited[m][n]` completely by modifying `board[i][j] = \'#\'` directly.\n7. `18ms`: check validity, e.g., `if(i > 0) dfs(...)`, before going to the next `dfs`.\n8. `17ms`: De-duplicate `c - a` with one variable `i`.\n9. `15ms`: Remove `HashSet` completely. dietpepsi\'s idea is awesome. \n\nThe final run time is `15ms`. Hope it helps!\n\n

\n\n public List findWords(char[][] board, String[] words) {\n List res = new ArrayList<>();\n TrieNode root = buildTrie(words);\n for (int i = 0; i < board.length; i++) {\n for (int j = 0; j < board[0].length; j++) {\n dfs (board, i, j, root, res);\n }\n }\n return res;\n }\n \n public void dfs(char[][] board, int i, int j, TrieNode p, List res) {\n char c = board[i][j];\n if (c == \'#\' || p.next[c - \'a\'] == null) return;\n p = p.next[c - \'a\'];\n if (p.word != null) { // found one\n res.add(p.word);\n p.word = null; // de-duplicate\n }\n\n board[i][j] = \'#\';\n if (i > 0) dfs(board, i - 1, j ,p, res); \n if (j > 0) dfs(board, i, j - 1, p, res);\n if (i < board.length - 1) dfs(board, i + 1, j, p, res); \n if (j < board[0].length - 1) dfs(board, i, j + 1, p, res); \n board[i][j] = c;\n }\n \n public TrieNode buildTrie(String[] words) {\n TrieNode root = new TrieNode();\n for (String w : words) {\n TrieNode p = root;\n for (char c : w.toCharArray()) {\n int i = c - \'a\';\n if (p.next[i] == null) p.next[i] = new TrieNode();\n p = p.next[i];\n }\n p.word = w;\n }\n return root;\n }\n \n class TrieNode {\n TrieNode[] next = new TrieNode[26];\n String word;\n }\n\n# Interview friendly version\nAs many folks asked, also attached my go-to version without many well thought optimizations. This version may be better for a quick solution in an interview.\n```\npublic List findWords(char[][] board, String[] words) {\n Trie trie = buildTrie(words);\n Set res = new HashSet<>();\n for (int i = 0; i < board.length; i++) {\n for (int j = 0; j < board[0].length; j++) {\n dfs(board, trie, res, i, j);\n }\n }\n return new ArrayList<>(res);\n}\n\npublic void dfs(char[][] board, Trie node, Set res, int i, int j) {\n if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || \n board[i][j] == \'#\' || node.next[board[i][j] - \'a\'] == null) {\n return;\n }\n if (node.next[board[i][j] - \'a\'].word != null) {\n res.add(node.next[board[i][j] - \'a\'].word);\n }\n\n // Go to next char\n node = node.next[board[i][j] - \'a\']; \n char c = board[i][j];\n board[i][j] = \'#\';\n dfs(board, node, res, i - 1, j);\n dfs(board, node, res, i + 1, j);\n dfs(board, node, res, i, j - 1);\n dfs(board, node, res, i, j + 1);\n board[i][j] = c;\n} \n\npublic Trie buildTrie(String[] words) {\n Trie root = new Trie();\n for (String w : words) {\n Trie p = root;\n for (char c : w.toCharArray()) {\n if (p.next[c - \'a\'] == null) {\n p.next[c - \'a\'] = new Trie();\n }\n p = p.next[c - \'a\']; // will point to curr char\n }\n p.word = w;\n }\n return root;\n}\n\nprivate class Trie {\n Trie[] next = new Trie[26];\n String word = null;\n}\n```\n\n [1]: http://algobox.org/word-search-ii/\n [2]: https://leetcode.com/discuss/36337/my-simple-and-clean-java-code-using-dfs-and-trie

Word Search II

Problem Description

Problem Description

Answer Panel