rajan published an article 2 months, 1 week ago |
In this article I'll implement a dictionary using Trie Data Structure. We'll discusss implementation of a dictionary using Trie (memory optimization using hash-map).
Let's take a problem and that requires dictionary to solve, this way we'll understand the in better way.
Problem
There are some name of students and we have their corresponding marks. Now the problem is to tell the marks of a student when his/her name is given as input.
Approach
There are other ways to solve this problem also but here, we'll store students and their marks in a dictionary.
Student name will be the key and his/her mark will be value.
We'll implement this dictionary using Trie. Trick is to add an extra data to the node of trie. i.e the mark of student. Whenever a new query is made, we'll search for that name of student in the Trie and if it is found, we'll return the value we are storing with it. Otherwise we'll return -1.
Implementation
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Structure for Trie
struct Trie {
bool isEndOfName;
unordered_map<char, Trie*> map;
int marks;
};
// Function to create a new Trie node
Trie* getNewTrieNode()
{
Trie* node = new Trie;
node->isEndOfName = false;
return node;
}
// Function to insert a student with its marks
// in the dictionary built using a Trie
void insert(Trie*& root, const string& str,
const int& marks)
{
// If root is null
if (root == NULL)
root = getNewTrieNode();
Trie* temp = root;
for (int i = 0; i < str.length(); i++) {
char x = str[i];
// Make a new node if there is no path
if (temp->map.find(x) == temp->map.end())
temp->map[x] = getNewTrieNode();
temp = temp->map[x];
}
// Mark end of Name and store the meaning
temp->isEndOfName = true;
temp->marks = marks;
}
// Function to search a student in the Trie and return its marks if it exists
string getMarks(Trie* root, const string& student)
{
// If root is null i.e. the dictionary is empty
if (root == NULL)
return "-1";
Trie* temp = root;
// Search a student in the Trie
for (int i = 0; i < student.length(); i++) {
temp = temp->map[student[i]];
if (temp == NULL)
return "-1";
}
// If it is the end of a valid name stored then return its marks
if (temp->isEndOfName)
return temp->marks;
return "-1";
}
// Main function
int main()
{
Trie* root = NULL;
// Build the dictionary
insert(root, "Alice", 80);
insert(root, "Pooja", 85);
insert(root, "Ramesh", 83);
insert(root, "Mark", 88);
string str = "Mark";
cout << getMarks(root, str);
return 0;
}
Output
88
arrow_upward Upvote |
Comment |
arrow_downward downvote |
HackersFriend Updates
Events
Python from zero to hero
place Bangalore ( HackersFriend office BTM Layout)