1: public class Trie { 2: private Node root;
3:
4: public Trie() { 5: root = new Node(' '); 6: }
7:
8: public void insert(String s) { 9: Node current = root;
10: if (s.length() == 0) // For an empty character
11: current.marker = true;
12: for (int i = 0; i < s.length(); i++) { 13: Node child = current.subNode(s.charAt(i));
14: if (child != null) { 15: current = child;
16: } else { 17: current.child.add(new Node(s.charAt(i)));
18: current = current.subNode(s.charAt(i));
19: }
20: // Set marker to indicate end of the word
21: if (i == s.length() - 1)
22: current.marker = true;
23: }
24: }
25:
26: public boolean search(String s) { 27: Node current = root;
28: while (current != null) { 29: for (int i = 0; i < s.length(); i++) { 30: if (current.subNode(s.charAt(i)) == null)
31: return false;
32: else
33: current = current.subNode(s.charAt(i));
34: }/*
35: * This means that a string exists, but make sure its a word by
36: * checking its 'marker' flag
37: */
38: if (current.marker == true)
39: return true;
40: else
41: return false;
42: }
43: return false;
44: }
45:
46: public List<String> searchPrefix(String s) { 47:
48: Node current = root;
49: if (current == null) { 50: return null;
51: }
52: List<String> list = new ArrayList<String>();
53: Node endNode = null;
54: StringBuilder endSB = new StringBuilder();
55: for (int i = 0; i < s.length(); i++) { 56: if (current.subNode(s.charAt(i)) == null) { 57: endNode = current;
58: break;
59: } else { 60: current = current.subNode(s.charAt(i));
61: endNode = current;
62: endSB.append(endNode.content);
63: }
64: }
65: if (endNode == null) { 66: return null;
67: }
68: if (endNode.marker == true) {// found as a word 69: list.add(endSB.toString());
70: }
71: // depth-first search the sub branch
72: Stack<Node> stack = new Stack<Node>();
73: stack.push(endNode);
74: while (!stack.isEmpty()) { 75: Node cur = stack.peek();
76: int needCount = cur.child.size();
77: for (Node node : cur.child) { 78: if (!node.visited) { 79: node.visited = true;
80: stack.push(node);
81: endSB.append(node.content);
82: if (node.marker) { 83: list.add(endSB.toString());
84: }
85: break;
86: } else { 87: needCount--;
88: }
89: }
90: if (needCount == 0) { 91: stack.pop();
92: endSB.deleteCharAt(endSB.length()-1);
93: }
94: }
95:
96: return list;
97: }
98:
99: public static void main(String[] args) { 100: Trie trie = new Trie();
101: trie.insert("ball"); 102: trie.insert("bat"); 103: trie.insert("dead"); 104: trie.insert("do"); 105: trie.insert("doll"); 106: trie.insert("dork"); 107: trie.insert("dorm"); 108: trie.insert("send"); 109: trie.insert("sense"); 110: List<String> list = trie.searchPrefix("d"); 111: for (String s : list) { 112: System.out.println(s);
113: }
114: }
115: }