Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Implementation
4.
Analysis Of Complexity
5.
FAQs
6.
Key Takeaways
Last Updated: Mar 27, 2024

Implement a Dictionary using Trie

Author dhruv sharma
1 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

The problem is based on Strings' Data Structure, which plays a vital role in solving various problems. We will be looking at a trie based efficient approach to solving the problem of storing and searching in a prebuilt dictionary.

So without any delays, let’s move on to our problem statement.

Problem Statement

In our problem, we will have to implement a dictionary with the help of a trie so that for a given string word input, the program prints its meaning from a prebuilt dictionary.

Example:
Input: programming
Output: Programming is the process of creating a set of instructions that tell a computer how to perform a task.
 

Example:
Input: computer
Output: A computer is a machine that can be programmed to carry out sequences of arithmetic or logical operations automatically.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Implementation

source

 

The approach will use the Trie Data Structure to store the words and their meanings. Using a dictionary, we can check whether prefixes exist or not.

# Python implementation of the approach

# Class for Trie
class Trie:
    
    def __init__(self):
        self.isWordsEnd = False
        self.listMap = dict()
        self.wordMeaning = ""
        
# For Creating a new Trie node
def createNewTrieNode():
    node = Trie()
    node.isWordsEnd = False
    return node
    
# For inserting word with its meaning in a dictionary built using Trie
def insertInTheTrie(root, givenStr, meaning):
    # If root is None
    if root is None:
        root = createNewTrieNode()
        
    temp = root
    
    for ch in givenStr:
        # if there is no path, make a new node
        if temp.listMap.get(ch) is None:
            temp.listMap[ch] = createNewTrieNode()
            
        temp = temp.listMap.get(ch)
        
    # store the meaning and mark end of a word 
    temp.isWordsEnd = True
    temp.wordMeaning = meaning
    return root
    
# For searching a word in the Trie and return its meaning if the word exists
def getWordMeaning(root, word):
    # If root is null i.e. the dictionary is empty
    if root is None:
        return "Found no meaning as word not present as root is None"
        
    temp = root
    # Search a word in the Trie
    for ch in word:
        temp = temp.listMap.get(ch)
        if temp is None:
            return "Found no meaning as word not present as char " + ch + " is None"
            
    # If it is the end of a valid word stored before then return its meaning
    if temp.isWordsEnd == True:
        return temp.wordMeaning
        
    return "Found no meaning as word not present!"
    
    
if __name__ == "__main__":
    
    root = None
    # Build the dictionary
    root = insertInTheTrie(root, "computer", '''A computer is a machine that can be instructed to carry out sequences of arithmetic or logical operations automatically via computer programming''')
    root = insertInTheTrie(root, "map", "a diagrammatic representation of an area")
    root = insertInTheTrie(root, "programming", "Programming is the process of creating a set of instructions that tell a computer how to perform a task")
    root = insertInTheTrie(root, "language", "the method of human communication")
    root = insertInTheTrie(root, "book", '''a written or printed work consisting of pages glued or sewn together along one side and bound in covers.''')
    root = insertInTheTrie(root, "science", '''the intellectual and practical activity encompassing the systematic study of the structure and behaviour of the physical and natural world through observation and experiment.''')
    givenStr = "computer"
    print(getWordMeaning(root, givenStr))

This approach will store the meaning of strings as we have added another property in the trie class used for keeping it.

Analysis Of Complexity

Time Complexity: To implement the approach, the Time complexity is O(word length).
Space Complexity: The space complexity to implement the approach is O(word length).

FAQs

  1. What is the Time and Space complexity to solve the above approach?
    The time complexity of the efficient approach is O(word length).
    The space complexity of the efficient approach is O(word length).
     
  2. What is the use of the Trie Data Structure?
    Trie is a search tree to locate specific keys within a map/set.

Key Takeaways

In this blog, we covered the following things:

  • Implementing a Trie based search and storing a prebuilt dictionary of items with their respective meanings.
  • The implementation uses a dictionary to check the prefixes in the Trie.

Try this problem to make the concept clear regarding the Trie data structure.

Also check out - Data Dictionary In Software Engineering

You can use Coding Ninjas Studio for various DSA questions typically asked in interviews for more practice. It will help you in mastering efficient coding techniques.

Happy Coding!!!

Previous article
Longest Common Prefix Matching
Next article
Container With Most Water
Live masterclass