Dado un Trie , la tarea es verificar si contiene palabras que comiencen con todos los alfabetos de [a – z] .
Ejemplos:
Entrada: teclas[] = {“elemento”, “niebla”, “genial”, “hola”,
“ok”, “ios”, “loro”, “prueba”, “kim”, “mango”, “naturaleza” , “manzana”,
“pelota”, “gato”, “perro”, “lima”, “ruby”, “brillo”, “tinkter”, “ultra”, “
volly”, “wow”, “xerox”, “ yak”, “zenon”, “broma”}
Salida: SíEntrada: teclas[] = {“geeks”, “for”, “geeks”}
Salida: No
Enfoque: solo necesitamos enfocarnos en el Node raíz del Trie dado y no es necesario atravesar otros Nodes. Simplemente verificamos si Trie tiene todos sus punteros secundarios que apuntan a Nodes válidos, es decir, hay palabras que comienzan con cada carácter del alfabeto.
A continuación se muestra la implementación del enfoque anterior:
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; const int ALPHABET_SIZE = 26; // Trie node struct TrieNode { struct TrieNode* children[ALPHABET_SIZE]; // isEndOfWord is true if the node represents // end of a word bool isEndOfWord; }; // Returns new trie node (initialized to NULL) struct TrieNode* getNode(void) { struct TrieNode* pNode = new TrieNode; pNode->isEndOfWord = false; for (int i = 0; i < ALPHABET_SIZE; i++) pNode->children[i] = NULL; return pNode; } // If not present, inserts key into trie // If the key is prefix of trie node, just // marks leaf node void insert(struct TrieNode* root, string key) { struct TrieNode* pCrawl = root; for (int i = 0; i < key.length(); i++) { int index = key[i] - 'a'; if (!pCrawl->children[index]) pCrawl->children[index] = getNode(); pCrawl = pCrawl->children[index]; } // Mark last node as leaf pCrawl->isEndOfWord = true; } // Function to check if Trie contains words // starting from all the alphabets bool containsAll(TrieNode* root) { // We check if root node has all childs // if None of them is NULL then we return true for (int i = 0; i < 26; i++) { // If there is no word in the trie starting // from the current alphabet if (root->children[i] == NULL) return false; } return true; } // Driver code int main() { string keys[] = { "element", "fog", "great", "hi", "ok", "ios", "parrot", "quiz", "kim", "mango", "nature", "apple", "ball", "cat", "dog", "lime", "ruby", "shine", "tinkter", "ultra", "volly", "wow", "xerox", "yak", "zenon", "joke" }; int n = sizeof(keys) / sizeof(keys[0]); // Create the Trie struct TrieNode* root = getNode(); for (int i = 0; i < n; i++) insert(root, keys[i]); // If trie contains words starting // from every alphabet if (containsAll(root)) cout << "Yes"; else cout << "No"; return 0; }
Yes