@@ -0,0 +1,2487 @@
+package leetcode201_210;%0A%0Aimport java.util.HashMap;%0A%0A/**Implement a trie with insert, search, and startsWith methods.%0A Note: You may assume that all inputs are consist of lowercase letters a-z.%0A * Created by eugene on 16/4/4.%0A */%0Apublic class ImplementTriePrefixTree %7B%0A%0A    //%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%8F%82%E8%80%83 http://www.programcreek.com/2014/05/leetcode-implement-trie-prefix-tree-java/%0A    class TrieNode %7B%0A        char c;%0A        HashMap%3CCharacter, TrieNode%3E children = new HashMap%3CCharacter, TrieNode%3E();%0A        boolean isLeaf;%0A%0A        public TrieNode() %7B%7D%0A        public TrieNode(char c)%7B%0A            this.c = c;%0A        %7D%0A    %7D%0A%0A    // Your Trie object will be instantiated and called as such:%0A    // Trie trie = new Trie();%0A    // trie.insert(%22somestring%22);%0A    // trie.search(%22key%22);%0A    public class Trie %7B%0A        private TrieNode root;%0A%0A        public Trie() %7B%0A            root = new TrieNode();%0A        %7D%0A%0A        // Inserts a word into the trie.%0A        public void insert(String word) %7B%0A            HashMap%3CCharacter, TrieNode%3E children = root.children;%0A            for(int i=0; i%3Cword.length(); i++)%7B%0A                char c = word.charAt(i);%0A                TrieNode t;%0A                if(children.containsKey(c))%7B%0A                    t = children.get(c);%0A                %7Delse%7B%0A                    t = new TrieNode(c);%0A                    children.put(c, t);%0A                %7D%0A                children = t.children;%0A                //set leaf node%0A                if(i==word.length()-1) t.isLeaf = true;%0A            %7D%0A        %7D%0A%0A        // Returns if the word is in the trie.%0A        public boolean search(String word) %7B%0A            TrieNode  t = searchNode(word);%0A            if (t!=null && t.isLeaf) return true;%0A            else return false;%0A        %7D%0A%0A        // Returns if there is any word in the trie%0A        // that starts with the given prefix.%0A        public boolean startsWith(String prefix) %7B%0A            if(searchNode(prefix) == null) return false;%0A            else return true;%0A        %7D%0A%0A        private TrieNode searchNode(String str)%7B%0A            HashMap%3CCharacter, TrieNode%3E children = root.children;%0A            TrieNode t = null;%0A            for(int i=0; i%3Cstr.length(); i++)%7B%0A                char c = str.charAt(i);%0A                if(children.containsKey(c))%7B%0A                    t = children.get(c);%0A                    children = t.children;%0A                %7Delse%7B%0A                    return null;%0A                %7D%0A            %7D%0A            return t;%0A        %7D%0A    %7D%0A%0A%7D%0A

Implement Trie (Prefix Tree)