import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
/**
* Implements a trie. We store the input list of words in tries so
* that we can efficiently find words with a given prefix.
*/
public class Trie {
// Trie Node
public static class Node {
//the character is the value of node
public char character;
public ArrayList children;
// end of a word
public boolean terminated = false;
public Node() {
children = new ArrayList();
}
public Node(char c) {
this();
character = c;
}
public boolean addWord(String w) {
if (w == null || w.length() == 0) {
return false;
}
Node child;
char firstChar = w.charAt(0);
Node tmp = getChild(firstChar);
if (tmp == null) {
child = new Node(firstChar);
children.add(child);
} else {
child = tmp;
}
if (w.length() > 1) {
child.addWord(w.substring(1));
} else {
child.terminated = true;
}
return true;
}
public Node getChild(char c) {
for (Node n : children) {
if (n.character == c)
return n;
}
return null;
}
public Node getLeafNode(char c) {
for (Node n : children) {
if (n.children.size() != 0) {
n.getLeafNode(c);
} else {
if (n.terminated) {
return n;
} else {
return null;
}
}
}
return null;
}
public Node getParentLeafNode(char c) {
for (Node n : children) {
if (n.children.size() != 0) {
n.getLeafNode(c);
} else {
if (n.terminated) {
return this;
} else {
return null;
}
}
}
return null;
}
public boolean removeChild(Node child) {
if (children.contains(child)) {
children.remove(child);
if (children.size() == 0) {
this.terminated = true;
}
return true;
} else {
return false;
}
}
public boolean removeChild(char c) {
Node child = new Node(c);
return removeChild(child);
}
public void getAllWords(StringBuilder path, ArrayList words) {
for (Node c : children) {
StringBuilder word = new StringBuilder(path);
word.append(c.character);
if (c.terminated) {
words.add(word.toString());
} else {
c.getAllWords(word, words);
}
}
}
} // end of TrieNode class
private Node root;
public Trie(ArrayList words) {
root = new Node();
for (String word : words) {
root.addWord(word);
}
}
public Trie(String[] words) {
root = new Node();
for (String word : words) {
root.addWord(word);
}
}
public boolean contains(String word, boolean exactMatch) {
Node current = root;
for (int i = 0; i < word.length(); i++) {
current = current.getChild(word.charAt(i));
if (current == null)
return false;
}
return !exactMatch || current.terminated;
}
public boolean removeWord(String w) {
if (contains(w, true)) {
for (int i = w.length() - 1; i >= 0; i--) {
char c = w.charAt(i);
Node parent = root.getParentLeafNode(c);
parent.removeChild(c);
if (parent.children.size() != 0) {
break;
}
}
} else {
return false;
}
return true;
}
public ArrayList getAllWords() {
ArrayList words = new ArrayList();
StringBuilder word = new StringBuilder();
root.getAllWords(word, words);
return words;
}
public void printTrie() {
Queue queue = new LinkedList(root.children);
Queue nextQueue = new LinkedList();
while (!queue.isEmpty()) {
Node n = queue.poll();
nextQueue.addAll(n.children);
System.out.print(n.character + " ");
if (queue.isEmpty()) {
queue.addAll(nextQueue);
nextQueue.clear();
System.out.println();
}
}
}
public static void main(String[] args) {
String[] words = {"apple", "arm", "grape", "apc"};
Trie root = new Trie(words);
ArrayList list = root.getAllWords();
root.printTrie();
System.out.println(list.toString());
System.out.println(root.contains("ppl", false));
System.out.println(root.contains("arm", true));
System.out.println(root.contains("appl", false));
}
}