String más larga en una array que coincide con el prefijo de la string dada

Dada una array de strings arr[] y consultas Q donde cada consulta consta de una string str , la tarea es encontrar la string más larga en la array que coincida con el prefijo de la string dada str , es decir, la string debe ser el prefijo de str .

Ejemplos:

Entrada: arr[] = {“GeeksForGeeks”, “GeeksForGeeksd”, “Arnab”, “Art”},
q[] = {“GeeksForGeeks”, “Ar”, “Art”}
Salida:
GeeksForGeeks
-1
Arte

Entrada: arr[] = {“Geek”, “Geek”, “Geekss”, “Geekk”},
q[] = {“Geek”, “Geeks”, “Geekk”, “Gee”}
Salida:
Geek
-1
Friki
-1

Enfoque ingenuo: para cada string dada, recorra la array y verifique la string que coincida con el prefijo de la string dada y almacene e imprima la string más larga.

Enfoque eficiente: este problema se puede resolver utilizando un Trie . Formaremos un trie e insertaremos las strings de la array en el trie y encontraremos la string más larga que coincida completamente con el prefijo de la string dada.

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 NULLs)
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();
  
        if (i == key.length() - 1)
  
            // Mark last node as leaf
            pCrawl->children[index]->isEndOfWord = true;
  
        pCrawl = pCrawl->children[index];
    }
}
  
string getString(char x)
{
    // string class has a constructor
    // that allows us to specify size of
    // string as first parameter and character
    // to be filled in given size as second
    // parameter.
    string s(1, x);
  
    return s;
}
  
// Function to return the
// longest required string
string search(struct TrieNode* root, string key)
{
    struct TrieNode* pCrawl = root;
  
    // Prefix of the string
    string s = "";
  
    for (int i = 0; i < key.length(); i++) {
        int index = key[i] - 'a';
        if (!pCrawl->children[index])
            break;
  
        s += getString((char)key[i]);
  
        pCrawl = pCrawl->children[index];
    }
  
    if (pCrawl->isEndOfWord)
        return s;
  
    return "-1";
}
  
// Driver code
int main()
{
    string arr[] = { "Geeks", "Geek",
                     "Geekss", "Geekks" };
    int n = sizeof(arr) / sizeof(string);
  
    // Construct trie
    struct TrieNode* root = getNode();
    for (int i = 0; i < n; i++)
        insert(root, arr[i]);
  
    string queries[] = { "Geek", "Geeks", "Geekk", "Gee" };
    int q = sizeof(queries) / sizeof(string);
  
    for (int i = 0; i < q; i++)
        cout << search(root, queries[i]) << endl;
  
    return 0;
}
Producción:

Geek
Geeks
-1
-1

Publicación traducida automáticamente

Artículo escrito por andrew1234 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 *