Saturday, May 5, 2012

Trie Implementation

[Question]
Implement a Trie.

[Analysis]
Trie: http://en.wikipedia.org/wiki/Trie


[Solution]

import java.util.*;

public class Trie {
Trie[]  nodes; //nodes of characters: a, b, ... z.
int[]   count;
boolean eow;    //end of word
boolean isLeaf;

public Trie() {
nodes = new Trie[26];
count = new int[26];
eow = false;
isLeaf = true;
}

public void addWord(String word) {
if (word==null || word.length()==0) return;

String temp= word.toLowerCase();
char[] chars = temp.toCharArray();
Trie p = this;
for(char c: chars) {
p.count[c-'a'] ++;
p.isLeaf = false;
if (p.nodes[c-'a'] == null) {
Trie node = new Trie();
p.nodes[c-'a'] = node;
}
p = p.nodes[c-'a'];
}
p.eow = true;
}

public boolean isWord(String word) {
String temp= word.toLowerCase();
char[] chars = temp.toCharArray();

Trie p = this;
for (char c: chars) {
if (p.nodes[c-'a'] == null) return false;
p = p.nodes[c-'a'];
}
return p.eow;
}

public void removeWord (String word) {
String temp = word.toLowerCase();

if (isWord (temp)) {
char[] chars = temp.toCharArray();

Trie p = this;
boolean flag = false;
for (char c: chars) {
p.count[c-'a']--;
if (p.count[c-'a'] == 0) {
p.nodes[c-'a'] = null;
flag = true;
break;
}
p = p.nodes[c-'a'];
}
if (!flag && p.eow) {
p.eow = false;
}
if (p.numOfWords() == 0) p.isLeaf = true;
}
}

public List<String> getAllWords() {
List<Character> path = new ArrayList<Character> ();
List<String>    words= new ArrayList<String>();
getAllWords(path, words);
return words;
}

public int numOfWords() {
int total =0;
for (int i: count) {
total+=i;
}
return total;
}

private void getAllWords(List<Character> path, List<String> words) {
if (eow) {
String s = "";
for (Character c: path) s+=c;
words.add(s);
}

if (isLeaf) return;

for (int i=0; i<nodes.length; i++) {
if (nodes[i]!=null) {
char c = Character.toChars('a'+i)[0];
path.add(c);
nodes[i].getAllWords(path, words);
path.remove(path.size()-1);
}
}
}
}

No comments:

Post a Comment