/** Initialize your data structure here. */ publicWordDictionary(){ root = new TrieNode(); } /** Adds a word into the data structure. */ publicvoidaddWord(String word){ TrieNode current = root; for (char c: word.toCharArray()) { if (!current.children.containsKey(c)) { current.children.put(c, new TrieNode()); } current = current.children.get(c); } current.isWord = true; } /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */ publicbooleansearch(String word){ return dfs(root, word); } booleandfs(TrieNode root, String word){ TrieNode current = root; for (int i = 0; i < word.length(); i++) { char c = word.charAt(i); if (c == '.') { for (TrieNode n: current.children.values()) { if (dfs(n, word.substring(i+1, word.length()))) { returntrue; } } returnfalse; } elseif(!current.children.containsKey(c)) { returnfalse; } current = current.children.get(c); } return current.isWord; } }
classTrieNode{ boolean isWord = false; Map<Character, TrieNode> children = new HashMap(); }
/** * Your WordDictionary object will be instantiated and called as such: * WordDictionary obj = new WordDictionary(); * obj.addWord(word); * boolean param_2 = obj.search(word); */