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