Question

Implement a dictionary application using C++ with the following features:

• Load a dictionary file.

• Given a prefix string that the user specifies, print the first word or all words in the dictionary with that string as their prefix.

• Given two strings A and B that the user specifies, replace all occurrences of A in the dictionary file with B.

• Spawning a new editor (e.g., vim) to allow the user to modify the dictionary file. Save the dictionary file afterwards.

You must use C++ to implement your dictionary application. All your source code must be put within one (1) file. You will only submit that one file.

Your program should not have any extra library dependencies.

All your source code must be put within one (1) file called dict.c or dict.cpp. You will then submit that one file to the submission system. No other files will be taken.

Your program should not have any extra library dependencies. Do not obfuscate the program.

Answer 1

// C++ implementation of the approach
#include <bits/stdc++.h>

using namespace std;

  
// Structure for Trie

struct Trie {

bool isEndOfWord;

unordered_map<char, Trie*> map;

string meaning;
};

  
// Function to create a new Trie node
Trie* getNewTrieNode()
{

Trie* node = new Trie;

node->isEndOfWord = false;

return node;
}

  
// Function to insert a word with its meaning
// in the dictionary built using a Trie

void insert(Trie*& root, const string& str,

const string& meaning)
{

  

// 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 word and store the meaning

temp->isEndOfWord = true;

temp->meaning = meaning;
}

  
// Function to search a word in the Trie
// and return its meaning if the word exists

string getMeaning(Trie* root, const string& word)
{

  

// If root is null i.e. the dictionary is empty

if (root == NULL)

return "";

  

Trie* temp = root;

  

// Search a word in the Trie

for (int i = 0; i < word.length(); i++) {

temp = temp->map[word[i]];

if (temp == NULL)

return "";

}

  

// If it is the end of a valid word stored

// before then return its meaning

if (temp->isEndOfWord)

return temp->meaning;

return "";
}

  
// Driver code

int main()
{

Trie* root = NULL;

  

// Build the dictionary

insert(root, "language", "the method of human communication");

insert(root, "computer", "A computer is a machine that can be \

instructed to carry out sequences of arithmetic or \
logical operations automatically via computer programming");

insert(root, "map", "a diagrammatic representation \
of an area");

insert(root, "book", "a written or printed work \
consisting of pages glued or sewn together along one \
side and bound in covers.");

insert(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.");

  

string str = "map";

cout << getMeaning(root, str);

  

return 0;
}
Output:
a diagrammatic representation of an area