Implemente un diccionario usando Trie de modo que si la entrada es una string que representa una palabra, el programa imprime su significado desde el diccionario preconstruido.
Ejemplos:
Entrada: str = “mapa”
Salida: una representación esquemática de un áreaEntrada: str = “idioma”
Salida: el método de comunicación humana
Enfoque: podemos usar un Trie para almacenar strings de manera eficiente y buscarlas. Aquí, se discute una implementación de un diccionario usando Trie (optimización de memoria usando hash-map). Agregamos otro campo al Node Trie, una string que contendrá el significado de una palabra. Mientras buscamos el significado de la palabra requerida, buscamos la palabra en Trie y si la palabra está presente (es decir, isEndOfWord = true), devolvemos su significado; de lo contrario, devolvemos una string vacía.
A continuación se muestra la implementación del enfoque anterior:
// 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; }
a diagrammatic representation of an area