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