In this article, we will learn about the trie data structure and its application in dictionary.

Table of Contents:

1. Introduction to Dictionary
2. Basic Operations of Trie
3. Dictionary using trie
4. Complexity Analysis
5. Other Solutions for Dictionary
6. Frequently Asked Questions

Introduction to Dictionary

We all know that dictionary is a book or electronic resource that lists the words along with their meanings of a particular language in alphabetical order. In terms of programming dictionary is actually a well defined data structure used for storing a group of objects. It contains a set of keys and each key has a single associated value. When the key the typed then the values is displayed.

Some of the most common operations on dictionaries are:

1. Deletion of a key-value pair
2. Retrieval of a value
3. Insertion/Update of a value
4. Searching for the existence of the particular key

We must keep in note that the values in dictionary are in unordered fashion, hence the loops over dictionaries will return items in the random order.
Before going into the depths of basic operations of trie, let's first take a look at the node structure that we are going to use for the implementation. So our Node will be defined in the following manner:

class Trie{
    public boolean endOfWord = false;
    public String meaning;
    public HashMap<Character,Trie> children = new HashMap<>();
}

1. A boolean type variable endOfWord that basically helps you in checking a new word character by character and then only add it along with its meaning.
2. A String type varible meaning to take input the meaning of the word to be added.
3. A HashMap children with Character type key and Node type value, it is used to map the new node created with the corresponding character.

Basic operations of Trie

1. Insertion of node in the trie

Following are the steps to insert word with its meaning in the trie
(a) Every letter of the word to be inserted is treated as an individual in the Trie node.
(b) The HashMap maps the given character of the word to the new node created.
(c) If the current node already has reference to the current letter, then simply set the current node to the referenced node, else create a new node and set the letter accordingly.
(d) Always remember that the length of word is the depth of the trie.

Here is the java code:

// Functions to insert new word with its meaning
// in the dictionary built using trie data structure
void insert(Trie root, String word, String meaning){
    if(root == null)
        getNewNode();

    Trie temp = root;
    for(int i = 0 ; i < word.length() ; i++){
        char x = word.charAt(i);

        // Making a new node in case there is no path
        if(temp.children.containsKey(x))
            temp = temp.children.get(x);

        temp.children.put(x, getNewNode());
    }
    // Mark end of word and store the meaning
    temp.endOfWord = true;
    temp.meaning = meaning;
}

2. Searching the word and displaying the meaning

Here are the steps:
(a) First check the initial conditions.
(b) Now check for the word using the children HashMap's key.
(c) If the word is present then simply return the meaning
(d) Else return an empty string

Here is the java code:

// Function to search a word in the trie and return its meaning
String getWordMeaning(Trie root, String word){
    if(root == null)
        return "";
    Trie temp = root;

    // Searching for a word in trie
    for(int i = 0 ; i < word.length() ; i++){
        temp = temp.children.get(word.charAt(i));
        if(temp == null)
            return "";
    }

    // if it is the end of valid word stored beforehand then
    // simply return its meaning
    if(temp.endOfWord)
        return temp.meaning;

    return "";
}

Dictionary using trie in Java

Here is the Java implementation of dictionary using trie:

import java.util.HashMap;
import java.util.Scanner;

class Trie{
public boolean endOfWord = false;
public String meaning;
public HashMap<Character,Trie> children = new HashMap<>();
}

public class Trie_Dictionary_With_Meaning {
// Function to create a new trie node
Trie getNewNode(){
   Trie node = new Trie();
   node.endOfWord = false;
   return node;
}

// Functions to insert new word with its meaning
// in the dictionary built using trie data structure
void insert(Trie root, String word, String meaning){
   if(root == null)
       getNewNode();

   Trie temp = root;
   for(int i = 0 ; i < word.length() ; i++){
       char x = word.charAt(i);

       // Making a new node in case there is no path
       if(temp.children.containsKey(x))
           temp = temp.children.get(x);

       temp.children.put(x, getNewNode());
   }
   // Mark end of word and store the meaning
   temp.endOfWord = true;
   temp.meaning = meaning;
}

// Function to search a word in the trie and return its meaning
String getWordMeaning(Trie root, String word){
   if(root == null)
       return "";
   Trie temp = root;

   // Searching for a word in trie
   for(int i = 0 ; i < word.length() ; i++){
       temp = temp.children.get(word.charAt(i));
       if(temp == null)
           return "";
   }

   // if it is the end of valid word stored beforehand then
   // simply return its meaning
   if(temp.endOfWord)
       return temp.meaning;

   return "";
}

public static void main(String[] args){
   Trie root = null;

   // Let's build the dictionary

   Trie_Dictionary_With_Meaning obj = new Trie_Dictionary_With_Meaning();

   Scanner sc = new Scanner(System.in);

   obj.insert(root, "Math", "A subject that deals in numbers");
   obj.insert(root, "map", "Diagrammatic representation of a particular area");
   obj.insert(root, "schedule", "A plan designed to execute a particular task");
   obj.insert(root, "book", "A written or printed work consisting of pages");
   System.out.println("Enter the word to be searched: ");
   String str = sc.next();
   System.out.println(obj.getWordMeaning(root, str));
}
}

Output

Enter the word to be searched:  
map
Diagrammatic representation of a particular area

Pseudo Code:

Step 1: START
Step 2: Creation of a class 'Trie' that corresponds to each node of the trie, it contains parent node, HashMap to map the characters and trie nodes and boolean type variable to mark end of the word.
Step 3: Create a method getNewNode() with Trie as return type to create a new node of type trie.
Step 3: Inserting a word with its meaning in the trie, for this we will create a method void insert()
(a) Every letter of the word to be inserted is treated as an individual in the Trie node.
(b) The HashMap maps the given character of the word to the new node created.
(c) If the current node already has reference to the current letter, then simply set the current node to the referenced node, else create a new node and set the letter accordingly.
(d) Always remember that the length of word is the depth of the trie.
Step 5: Now let's define a method for finding meaning, String getWordMeaning()
(a) First check the initial conditions.
(b) Now check for the word using the children HashMap's key.
(c) If the word is present then simply return the meaning
(d) Else return an empty string
Step 6: Now in the main method, first add some words with their meanings in the dictionary, then search for the desired word and print the result accordingly.
Step 7: STOP

Complexity Analysis

Time Complexity Analysis:

1. Insertion: We see that for inserting a new word in the dictionary, a for loop is used that runs from first character to the last character of the word and the conditions are checked accordingly, therefore the time complexity for the insertion operation will be O(word length).
2. Searching: In case of searching also we have used a for loop that basically checks for the word character by character and returns the corresponding meaning upon finding the word, therfore the time complexity for seaching opeartion will be O(word length) as well.

Space Complexity Analysis:

For both operations insertion and searching we need a string to insert the word and return the meaning respectively, therefore the space complexity will be O(word length).

Other Solutions for Dictionary

Dictionary class in Java
Java provides its users an in-built abstract class Dictionary in the utility package. The util.Dictionary class is basically a key-value relation and works similar like a map.

Here is the implementation of dictionary class in Java:

import java.util.Dictionary;
import java.util.Hashtable;
import java.util.Scanner;

public class Opengenus_DictionaryClass {
public static void main(String[] args){
    Dictionary<String, String> dictionary = new Hashtable<>();
    dictionary.put("Map", "Pictorial representation of an area");
    dictionary.put("gender", "sexual orientation of a person");
    dictionary.put("book", "A collection of pages clubbed together for a particular subject");
    dictionary.put("computer", "An electronic device used for computational and high end purposes");
    dictionary.put("cricket", "An insect");

    System.out.println("Enter the word to be searched: ");
    Scanner sc = new Scanner(System.in);
    String word = sc.next();
    String meaning = dictionary.get(word);
    if(meaning.isEmpty())
        System.out.println("Not Found!");
    else
        System.out.println(meaning);
}
}

Output

Enter the word to be searched: 
book
A collection of pages clubbed together for a particular subject 

Dictionary in Python
Dictionaries in python are used to store data values in key-value pairs. Duplicates are not allowed and the values are ordered and changeable.
Here is a sample code:

thisdict = {
"book": "Chronicles of Narnia",
"unique": "something not ordinary",
"human": "A living species",
 }
print(thisdict)

Output

{'book': 'Chronicles of Narnia', 'unique': 'something not ordinary', 'human': 'A living species'}

Frequently Asked Questions

1. What is meaning of word 'trie'?
Ans: The word 'trie' means retrieval.
2. List some uses of trie data structure?
Ans: Trie data structure is used in auto-completion, browsing history, spell checking and longest prefix matching.
3. What is the maximum number of points a node can have in alphbetic trie?
Ans: 26
4. What does root node correspond to in Trie?
Ans: The root node in trie corresponds to null.
5. How many letters can a node store in trie?
Ans: 1

Thank You!