@@ -0,0 +1,1411 @@
+package problems;%0A%0Aimport java.util.HashMap;%0A%0Apublic class Trie %7B%0A%0A    private Node root;%0A%0A    public Trie() %7B%0A        root = new Node((char) 0);%0A    %7D%0A%0A    public class Node %7B%0A        final char ch;%0A        boolean end;%0A        final HashMap%3CCharacter, Node%3E child;%0A%0A        public Node(char c) %7B%0A            this.ch = c;%0A            child = new HashMap%3CCharacter, Node%3E();%0A        %7D%0A    %7D%0A%0A    public Node insert(String s) %7B%0A        Node n = root;%0A        for (int i = 0; i %3C s.length(); i++) %7B%0A            char a = s.charAt(i);%0A            if (n.child.containsKey(a))%0A                n = n.child.get(a);%0A            else %7B%0A                Node newNode = new Node(a);%0A                n.child.put(a, newNode);%0A                n = newNode;%0A            %7D%0A        %7D%0A        n.end = true;%0A        return n;%0A    %7D%0A%0A    public String longestMatch(String s) %7B%0A        String out = %22%22;%0A        Node n = root;%0A%0A        for (int i = 0; i %3C s.length(); i++) %7B%0A            char c = s.charAt(i);%0A            if (n.child.containsKey(c)) %7B%0A                out += c;%0A                n = n.child.get(c);%0A            %7D else%0A                break;%0A        %7D%0A        return out;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A%0A        Trie trie = new Trie();%0A%0A        String%5B%5D a = %7B %22ra%22, %22rob%22, %22rooc%22 %7D;%0A        for (String s : a)%0A            trie.insert(s);%0A%0A        System.out.println(trie.longestMatch(%22roab%22));%0A    %7D%0A%7D%0A

Add Trie for finding longest matching prefix