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
ArteEntrada: 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; }
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