1 public class Solution {
  2 
  3     public static void main(String[] args) {
  4         Trie trie = new Trie();
  5         trie.insert("apple");
  6         trie.insert("pie");
  7         trie.insert("applejuice");
  8         trie.insert("juice");
  9 
 10         Solution s = new Solution();
 11         s.buzz("applepiejuice", trie.root);
 12     }
 13 
 14     public void buzz(String str, Node root) {
 15         List<Node> list = new ArrayList<Node>();
 16         List<Node> temp = new ArrayList<Node>();
 17         list.add(root);
 18         for (int i = 0; i < str.length(); i++) {
 19             for (Node node : list) {
 20                 Node child = node.getChildNode(str.charAt(i));
 21                 if (child != null) {
 22                     temp.add(child);
 23                     if (child.isEnd) {
 24                         System.out.println("buzz");
 25                     }
 26                 }
 27             }
 28             if (i != 0) {
 29                 Node child = root.getChildNode(str.charAt(i));
 30                 if (child != null) {
 31                     temp.add(child);
 32                     if (child.isEnd) {
 33                         System.out.println("buzz");
 34                     }
 35                 }
 36             }
 37 
 38             list = temp;
 39             temp = new ArrayList<Node>();
 40         }
 41 
 42     }
 43 }
 44 
 45 class Trie {
 46     Node root;
 47 
 48     public Trie() {
 49         root = new Node(‘ ‘);
 50     }
 51 
 52     public void insert(String word) {
 53         if (exists(word))
 54             return;
 55         Node current = root;
 56         for (int i = 0; i < word.length(); i++) {
 57             char ch = word.charAt(i);
 58             Node node = current.getChildNode(ch);
 59             if (node == null) {
 60                 current.map.put(ch, new Node(ch));
 61                 current = current.getChildNode(ch);
 62             } else {
 63                 current = node;
 64             }
 65         }
 66         current.isEnd = true;
 67     }
 68 
 69     public boolean exists(String word) {
 70         Node current = root;
 71         for (int i = 0; i < word.length(); i++) {
 72             char ch = word.charAt(i);
 73             current = current.getChildNode(ch);
 74             if (current == null) {
 75                 return false;
 76             }
 77         }
 78         if (current.isEnd) {
 79             return true;
 80         } else {
 81             return false;
 82         }
 83     }
 84 
 85 }
 86 
 87 class Node {
 88     char ch;
 89     boolean isEnd;
 90     Map<Character, Node> map;
 91 
 92     public Node(char ch) {
 93         this.ch = ch;
 94         map = new HashMap<Character, Node>();
 95     }
 96 
 97     public Node getChildNode(char ch) {
 98         return map.get(ch);
 99     }
100 }