Implement a Dictionary using Trie

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!!!