public
Created

Trie

  • Download Gist
gistfile1.java
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94
class Node{
public char d;public boolean e;
public LinkedList<Node>c;
public Node(){}
public Node(char a){d=a;e=Boolean.FALSE;c=new LinkedList<Node>();}
public Node sub(char a){
int i;
if(c.isEmpty()) return null;
for(i=0;i<c.size();i++)
if(c.get(i).d==a) return c.get(i);
return null;
}
}
class Trie{
Node root;
public Trie(){
root=new Node(' ');
}
public void add(String a){
Node n,cur=root;int len=a.length(),i,j;
if(len==0) cur.e=Boolean.TRUE;
else{
for(i=0;i<len;i++){
if(cur.sub(a.charAt(i))==null) break;
cur=cur.sub(a.charAt(i));
}
while(i<len){
n=new Node(a.charAt(i));
cur.c.add(n);
cur=cur.sub(a.charAt(i));
i++;
}
cur.e=Boolean.TRUE;
}
}
public boolean search(String a){
Node cur=root;int i,j,len=a.length();
for(i=0;i<len;i++) {
if(cur.sub(a.charAt(i))==null) return Boolean.FALSE;
cur=cur.sub(a.charAt(i));
}
if(i==len) return Boolean.TRUE;
return Boolean.FALSE;
}
public boolean searchw(String a){
Node cur=root;int i,j,len=a.length();
for(i=0;i<len;i++) {
if(cur.sub(a.charAt(i))==null) return Boolean.FALSE;
cur=cur.sub(a.charAt(i));
}
return cur.e;
}
public String next(String pre){
Node cur=root;int i,len=pre.length();
for(i=0;i<len;i++) {
if(cur.sub(pre.charAt(i))==null) return "";
cur=cur.sub(pre.charAt(i));
}
String res="";
if(i==len) {
for(Node a:cur.c)
res=res+String.valueOf(a.d);
return res;
}
return "";
}
public LinkedList<Node> getnode(String pre){
Node cur=root;int i,j,len=pre.length();
for(i=0;i<len;i++) {
if(cur.sub(pre.charAt(i))==null) return null;
cur=cur.sub(pre.charAt(i));
}
if(i==len) return cur.c;
return null;
}
public Vector<String>all=new Vector<String>();
String tm;
public Vector<String> getStrings(String pre){
rec(pre);
return all;
//for(String f:all) System.out.println(f);
//System.out.println(all.size());
}
public void rec(String pr){
LinkedList<Node>nod=getnode(pr);
for(Node n:nod){
tm=pr+String.valueOf(n.d);
if(n.e) {all.add(tm);}
else {
rec(tm);
}
}
}
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.