I need to use a Trie tree in a job and I need specific methods Insert , Search , Delete , StartWith . But I am trying to create a method similar to StartWith but return a vector of Strings that contain all the words found in the tree that begin with the letters that are entered. Below the current code:
class TrieNode {
TrieNode[] arr;
boolean isEnd;
int qtd;
// Inicia um Nodo com 26 posições. Cada uma relativa a um letra do alfabeto.
public TrieNode() {
this.arr = new TrieNode[26];
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
/**
* Insere uma palavra na arvore, tornando uma posição do nodo não nula
* indicando qual char ela representa atraves do index.
* @param word: palavra a ser inserida na arvore.
*/
public void insert(String word) {
TrieNode p = root;
for(int i=0; i<word.length(); i++){
char c = word.charAt(i);
//subtrai 'a' que corresponde a 97 na tabela ascii para verificar seu
//corresponde[0=a; 1=b]
int index = c-'a';
if(p.arr[index]==null){
TrieNode temp = new TrieNode();
p.arr[index]=temp;
p = temp;
}else{
p=p.arr[index];
}
}
p.isEnd=true;
p.qtd++;
}
/**
*
* @param word palavra a ser pesquisada.
* @return true se a palavra existe na arvore
* ou falso caso não existe.
*/
public boolean search(String word) {
TrieNode p = searchNode(word);
if(p==null){
return false;
}else{
if(p.isEnd)
return true;
}
return false;
}
//retorna true caso tenha alguma palavra na arvore com o prefixo informado
public boolean startsWith(String prefix) {
TrieNode p = searchNode(prefix);
if(p==null){
return false;
}else{
return true;
}
}
public TrieNode searchNode(String s){
TrieNode p = root;
for(int i=0; i<s.length(); i++){
char c= s.charAt(i);
int index = c-'a';
if(p.arr[index]!=null){
p = p.arr[index];
}else{
return null;
}
}
if(p==root)
return null;
return p;
}
//devolve quantas palavras S tem na arvore no formato: palavra[quantidade]
public String searchWithIndex(String s){
String texto = "";
TrieNode p = root;
for(int i=0; i<s.length(); i++){
char c= s.charAt(i);
int index = c-'a';
if(p.arr[index]!=null){
texto+=(char)(index+97);
p = p.arr[index];
}else{
return null;
}
}
return texto + "["+p.qtd+"]" ;
}
}
I am in doubt whether it is easiest to try to create this method with vector or with ArrayList, and how it would be done given the way the tree was implemented. This site implements the same tree using HashMap.