Java HashMap backed Trie
Here is working Trie implementation that uses the HashMap for storing the references to the next nodes.\n\n    public class WordDictionary {\n    \n    private 
Here is working Trie implementation that uses the HashMap for storing the references to the next nodes.\n\n    public class WordDictionary {\n    \n    private static final char WILDCARD = '.';\n\n    private final TrieNode root = new TrieNode();\n\n    // Adds a word into the data structure.\n    public void addWord(String word) {\n\n        insert(root, word);\n    }\n\n    // Returns if the word is in the data structure. A word could\n    // contain the dot character '.' to represent any one letter.\n    public boolean search(String word) {\n\n        return search(root, word, 0);\n    }\n    \n    private void insert(TrieNode root, String word) {\n\n        TrieNode node = root;\n        for(int ind = 0; ind < word.length(); ind++) {\n            final char c = word.charAt(ind);\n            if(!node.next.containsKey(c)) {\n                node.next.put(c, new TrieNode());\n            }\n            node = node.next.get(c);\n        }\n        node.isWordEnd = true;\n    }\n\n    private boolean search(TrieNode node, String word, int len) {\n\n        if(node == null) {\n            return false;\n        }\n        if(len == word.length()) {\n            return node.isWordEnd;\n        }\n        final char c = word.charAt(len);\n        if(isWildcard(c)) {\n            for(TrieNode next : node.next.values()) {\n                if(search(next, word, len + 1)) {\n                    return true;\n                }\n            }\n            return false;\n        } else {\n            return search(node.next.get(c), word, len + 1);\n        }\n    }\n\n    private boolean isWildcard(char c) {\n        return c == WILDCARD;\n    }\n\n    private static class TrieNode {\n\n        private final Map<Character, TrieNode> next = new HashMap<>();\n        private boolean isWordEnd;\n    }\n    }
[]