@@ -0,0 +1,2527 @@
+import java.util.HashMap;%0A%0Aclass TrieNode %7B%0A    char letter;%0A    HashMap%3CCharacter, TrieNode%3E nodes;%0A    public TrieNode(char letter) %7B%0A        this.letter = letter;%0A        nodes = new HashMap%3C%3E();%0A    %7D%0A%0A    @Override%0A    public boolean equals(Object o) %7B%0A        if (this == o) return true;%0A        if (o == null %7C%7C getClass() != o.getClass()) return false;%0A%0A        TrieNode trieNode = (TrieNode) o;%0A%0A        if (letter != trieNode.letter) return false;%0A        if (nodes.size() != trieNode.nodes.size()) return false;%0A        for(char c : nodes.keySet())%7B%0A            return trieNode.contains(c) && nodes.get(c).equals(trieNode.nodes.get(c));%0A        %7D%0A        return true;%0A    %7D%0A%0A    @Override%0A    public int hashCode() %7B%0A        int result = letter;%0A        result = 31 * result + (nodes != null ? nodes.hashCode() : 0);%0A        result = 31 * result + (nodes != null ? nodes.hashCode() : 0);%0A        return result;%0A    %7D%0A%0A    public TrieNode add(TrieNode node)%7B%0A        if(nodes.containsKey(node.letter)) return nodes.get(node.letter);%0A        else %7B%0A            nodes.put(node.letter, node);%0A            return node;%0A        %7D%0A    %7D%0A%0A    public boolean contains(char letter)%7B%0A        return nodes.containsKey(letter);%0A    %7D%0A%7D%0A%0Apublic class Trie %7B%0A    // Special Word Ending Character%0A    private char endingWordCharacter = '~';%0A    private TrieNode root;%0A%0A    public Trie() %7B%0A        root = new TrieNode(endingWordCharacter);%0A    %7D%0A%0A    public void insert(String word) %7B%0A        word = word + endingWordCharacter;%0A        TrieNode tail = null;%0A        for (int i = 0; i %3C word.length(); i++) %7B%0A            if (i == 0) %7B%0A                tail = root.add(new TrieNode(word.charAt(i)));%0A            %7D else %7B%0A                tail = tail.add(new TrieNode(word.charAt(i)));%0A            %7D%0A        %7D%0A    %7D%0A%0A    public boolean search(String word) %7B%0A        return startsWith(word + endingWordCharacter);%0A    %7D%0A%0A    public boolean startsWith(String prefix) %7B%0A        TrieNode prev = null;%0A        for (int i = 0; i %3C prefix.length(); i++) %7B%0A            if (i == 0) %7B%0A                if (!root.contains(prefix.charAt(i))) %7B%0A                    return false;%0A                %7D else %7B%0A                    prev = root.nodes.get(prefix.charAt(i));%0A                %7D%0A            %7D else %7B%0A                if (!prev.contains(prefix.charAt(i))) %7B%0A                    return false;%0A                %7D else %7B%0A                    prev = prev.nodes.get(prefix.charAt(i));%0A                %7D%0A            %7D%0A        %7D%0A        return true;%0A    %7D%0A%0A%7D%0A

Create Trie.java