patternjavaMinor
Trie for lowercase words
Viewed 0 times
wordslowercasefortrie
Problem
I need to develop a dictionary program so I used a trie data structure to implement it. I have created a array of object with size of 26 - so each object of class
This program takes no input from user for now. I gave my input in main function. but it will print all the words in the trie.
This program works fine. Is this program somewhat efficient? do I have to replace the fixed sized array of object of class
```
public class Dict {
boolean isWord;
Dict obj[];
Dict()
{
obj=new Dict[26]; // as there are 26 letters in english
isWord=false;
}
Dict insertWord(Dict Node,String str, int it) // used to insert a word into trie
{
if(it<str.length())
{
int Linkno=((int)(str.charAt(it)))-97; //97 is the ascii value of 'a'.
if(Node.obj[Linkno]==null)
{
Node.obj[Linkno]=new Dict();
}
insertWord(Node.obj[Linkno],str,it+1);
}
else
{
Node.isWord=true;
}
return Node;
}
void displayAll(Dict Node,String str) // used to display all the words in the trie
{
for(int i=0;i<26;i++)
{
if(Node.obj[i]!=null)
{
if(Node.obj[i].isWord==true)
System.out.println(str+((char)(i+97)));
displayAll(Node.obj[i],(str+((char)(i+97))));
}
}
}
public static void main(String ar[])
{
Dict root=new Dict();
root.insertWord(root,"trasaction",0);
root.insertWord(root,"transformation",0);
root.insertWord(root,"transmission",0);
root.insertWord(root,"trance",0);
root.insertWord(root,"trap",0);
root.displayAll(r
Dict will have 26 sub objects like a child.This program takes no input from user for now. I gave my input in main function. but it will print all the words in the trie.
This program works fine. Is this program somewhat efficient? do I have to replace the fixed sized array of object of class
Dict with any other technique?```
public class Dict {
boolean isWord;
Dict obj[];
Dict()
{
obj=new Dict[26]; // as there are 26 letters in english
isWord=false;
}
Dict insertWord(Dict Node,String str, int it) // used to insert a word into trie
{
if(it<str.length())
{
int Linkno=((int)(str.charAt(it)))-97; //97 is the ascii value of 'a'.
if(Node.obj[Linkno]==null)
{
Node.obj[Linkno]=new Dict();
}
insertWord(Node.obj[Linkno],str,it+1);
}
else
{
Node.isWord=true;
}
return Node;
}
void displayAll(Dict Node,String str) // used to display all the words in the trie
{
for(int i=0;i<26;i++)
{
if(Node.obj[i]!=null)
{
if(Node.obj[i].isWord==true)
System.out.println(str+((char)(i+97)));
displayAll(Node.obj[i],(str+((char)(i+97))));
}
}
}
public static void main(String ar[])
{
Dict root=new Dict();
root.insertWord(root,"trasaction",0);
root.insertWord(root,"transformation",0);
root.insertWord(root,"transmission",0);
root.insertWord(root,"trance",0);
root.insertWord(root,"trap",0);
root.displayAll(r
Solution
Do I have to replace the fixed sized array of object of class Dict with any other technique?
I suggest making the size a constant, like this:
And then you may use:
As you can see, the comment now becomes redundant and we can remove it, and it is always a good thing, as comments may become obsolete or wrong.
The same applies to:
Make a constant:
Get rid of repetition
Looking at:
What if you want to add 10 more words? The code will become very long and repetitive, instead use a foreach loop:
Miscellanous
-
Wrong indent hurts readibility, fix it in:
-
Always use braces to prevent bugs in :
-
Avoid general names like
I suggest making the size a constant, like this:
public static int ALPHABET_SIZE = 26:And then you may use:
obj = new Dict[ALPHABET_SIZE];As you can see, the comment now becomes redundant and we can remove it, and it is always a good thing, as comments may become obsolete or wrong.
The same applies to:
int Linkno=((int)(str.charAt(it)))-97; //97 is the ascii value of 'a'.Make a constant:
LOWER_A_ASCII_VAL = 97;Get rid of repetition
Looking at:
root.insertWord(root,"trasaction",0);
root.insertWord(root,"transformation",0);
root.insertWord(root,"transmission",0);
root.insertWord(root,"trance",0);
root.insertWord(root,"trap",0);What if you want to add 10 more words? The code will become very long and repetitive, instead use a foreach loop:
for (String word : {"transaction", "transformation", ...} ) {
root.insertWord(root, word, 0);
}Miscellanous
-
Wrong indent hurts readibility, fix it in:
if(it<str.length())
{
int Linkno=((int)(str.charAt(it)))-97; //97 is the ascii value of 'a'.
if(Node.obj[Linkno]==null)
{
Node.obj[Linkno]=new Dict();
}
insertWord(Node.obj[Linkno],str,it+1);
}-
Always use braces to prevent bugs in :
if(Node.obj[i].isWord==true) {
System.out.println(str+((char)(i+97)));
}-
Avoid general names like
obj and think about a more precise name.Code Snippets
public static int ALPHABET_SIZE = 26:obj = new Dict[ALPHABET_SIZE];int Linkno=((int)(str.charAt(it)))-97; //97 is the ascii value of 'a'.LOWER_A_ASCII_VAL = 97;root.insertWord(root,"trasaction",0);
root.insertWord(root,"transformation",0);
root.insertWord(root,"transmission",0);
root.insertWord(root,"trance",0);
root.insertWord(root,"trap",0);Context
StackExchange Code Review Q#106327, answer score: 2
Revisions (0)
No revisions yet.