Skip to content

Instantly share code, notes, and snippets.

@bknarendra
Created July 8, 2012 18:26
Show Gist options
  • Save bknarendra/3072190 to your computer and use it in GitHub Desktop.
Save bknarendra/3072190 to your computer and use it in GitHub Desktop.
Trie
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);
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment