Trie is a very useful data structure. It finds many uses in string based applications like dictionary, autocomplete, spell check etc.

This blog post is not a tutorial on trie but I am simply sharing my trie implementation in java here.

You could find many other implementations on the internet but I really struggled understanding the other implementations especially the function of getting complete words matching a prefix. So I decided to write my own. Here is my implementation.

You can also find it here

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); } } } }

## 0 comments:

## Post a Comment