Java || Trie || buildDict - O(dictionary.length*dictionary[i].length) || search - O(26*word.length)
public class Trie {\n\n\tprivate class Node {\n\n\t\tchar data;\n\t\tNode[] children;\n\t\tboolean isTerminal;\n\n\t\tpublic Node(char data, boolean isTerminal)
public class Trie {\n\n\tprivate class Node {\n\n\t\tchar data;\n\t\tNode[] children;\n\t\tboolean isTerminal;\n\n\t\tpublic Node(char data, boolean isTerminal) {\n\t\t\tthis.data = data;\n\t\t\tthis.isTerminal = isTerminal;\n\t\t\tthis.children = new Node[26];\n\t\t}\n\n\t}\n\n\tprivate Node root;\n\n\t// O(1)\n\tpublic Trie() {\n\t\tthis.root = new Node(\'\\0\', false);\n\t}\n\n\t// O(word.length)\n\tpublic void addWord(String word) {\n\t\tNode curr = root;\n\t\tfor (char ch : word.toCharArray()) {\n\t\t\tNode temp = curr.children[ch - \'a\'];\n\t\t\tif (temp == null) {\n\t\t\t\ttemp = new Node(ch, false);\n\t\t\t\tcurr.children[ch - \'a\'] = temp;\n\t\t\t}\n\t\t\tcurr = temp;\n\t\t}\n\t\tcurr.isTerminal = true;\n\t}\n\n\t// O(word.length)\n\tpublic boolean searchWord(String word) {\n\t\treturn searchWord(root, word, 0, 0);\n\t}\n\n\t// O(word.length)\n\tprivate boolean searchWord(Node root, String word, int count, int vidx) {\n\n\t\tif (count == 2)\n\t\t\treturn false;\n\n\t\tif (vidx == word.length())\n\t\t\t\treturn (count == 1 && root.isTerminal) ? true : false;\n            \n\t\tchar ch = word.charAt(vidx);\n\t\tfor (int i = 0; i < 26; i++) {\n\t\t\tif (root.children[i] != null) {\n\t\t\t\tchar temp = (char) (i + \'a\');\n\t\t\t\tint ncount = (ch == temp) ? count : count + 1;\n\t\t\t\tif (searchWord(root.children[i], word, ncount, vidx + 1))\n\t\t\t\t\treturn true;\n\t\t\t}\n\t\t}\n\t\treturn false;\n\t}\n\n}\n\nclass MagicDictionary {\n\n\tTrie trie;\n\n\t// O(1)\n\tpublic MagicDictionary() {\n\t\ttrie = new Trie();\n\t}\n\n\t// O(dictionary.length*dictionary[i].length)\n\tpublic void buildDict(String[] dictionary) {\n\t\tfor (String word : dictionary)\n\t\t\ttrie.addWord(word);\n\t}\n\n\t// O(word.length)\n\tpublic boolean search(String searchWord) {\n\t\treturn trie.searchWord(searchWord);\n\t}\n}\n
[]