Compruebe si el Trie dado contiene palabras que comienzan con todos los alfabetos

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:

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;
}
Producción:

Yes

Publicación traducida automáticamente

Artículo escrito por prajmsidc y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *