HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Trie for lowercase words

Submitted by: @import:stackexchange-codereview··
0
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 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:

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.