Dada una array arr[] que consta de N strings y Q consultas en forma de prefijo y sufijo de dos strings , la tarea de cada consulta es encontrar cualquier string en la array dada con el prefijo y el sufijo dados . Si no existe tal string, imprima «-1» .
Ejemplos:
Entrada: arr[] = {“manzana”, “aplicación”, “galleta”, “ratón”, “naranja”, “murciélago”, “micrófono”, “mío”}, Consultas[] = {{a, e} , {a, p}}
Salida: aplicación de
manzana Explicación: Consulta 1: la string «manzana» es la única palabra en el diccionario dado con el prefijo «a» y el sufijo «e». Consulta 2: la string «aplicación» es la única palabra en el diccionario dado con el prefijo «a» y el sufijo «p» dados.
Entrada: arr[] = {“manzana”, “aplicación”, “galleta”, “ratón”, “naranja”, “murciélago”, “micrófono”, “mío”}, Consultas[] = {{mi, ne} }
Salida: mía
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es recorrer la array dada de strings arr[] para cada consulta y, si existe tal string con el prefijo y el sufijo dados, luego imprimir esa string. De lo contrario, imprima «-1» .
Complejidad de tiempo: O(Q*N*M), donde M es la longitud máxima de la string .
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso de la estructura de datos Trie para resolver el problema. La implementación de trie se puede modificar para admitir la búsqueda de prefijos y sufijos de la siguiente manera:
- Supongamos que la palabra dada en un diccionario es manzana . En este caso, la palabra manzana se inserta en el Trie. Pero para admitir la búsqueda de prefijos y sufijos simultáneamente, las palabras: e{apple, le{apple, ple{apple, pple{apple, apple{apple) se pueden insertar en el Trie.
- Tenga en cuenta que estas palabras tienen la forma sufijo{palabra donde sufijo son todos los sufijos posibles de la palabra dada.
- El carácter especial { se inserta entre el sufijo y la palabra para separarlos. Se puede usar cualquier carácter especial que no sea el alfabeto en lugar de { , pero se prefiere { porque su valor ASCII es 123, que es uno más que el valor ASCII de z .
Siga los pasos a continuación para resolver el problema:
- Recorra todas las strings en el arreglo arr[] usando la variable i y realice los siguientes pasos:
- Inicializa una string, temp como ‘{‘ + arr[i] .
- Itere sobre todos los caracteres en la string , arr[i] desde el final, para cada carácter , agréguelo al frente de la string temporal y luego inserte esta string en el trie .
- Después de la creación del trie, itere sobre todas las consultas y realice los siguientes pasos:
- Almacene la string de prefijo y sufijo para la consulta actual.
- Inicialice una string, t como sufijo + ‘{‘ + prefijo y búsquelo en el trie .
- Si no se encuentra, imprima “-1” . De lo contrario, imprima la string correspondiente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Trie Node
struct Trie {
Trie* arr[27] = { NULL };
// Stores the index of the word
// in the dictionary
int idx;
};
// Root node of the Trie
Trie* root = new Trie();
// Function to insert the words in
// the Trie
void insert(string word, int i)
{
// Temporary pointer to the root
// node of the Trie
Trie* temp = root;
// Traverse through all the
// characters of current word
for (char ch : word) {
// Make a Trie Node, if not
// already present
if (temp->arr[ch - 'a'] == NULL) {
Trie* t = new Trie();
temp->arr[ch - 'a'] = t;
}
temp = temp->arr[ch - 'a'];
temp->idx = i;
}
}
// Function to search the words in Trie
int search(string word)
{
Trie* temp = root;
// Traverse through all the
// characters of current word
for (char ch : word) {
// If no valid Trie Node exists
// for the current character
// then there is no match
if (temp->arr[ch - 'a'] == NULL)
return -1;
temp = temp->arr[ch - 'a'];
}
// Return the resultant index
return temp->idx;
}
// Function to search for a word in
// the dictionary with the given
// prefix and suffix for each query
void findMatchingString(
string words[], int n,
vector<vector<string> > Q)
{
string temp, t;
// Insertion in the Trie
for (int i = 0; i < n; i++) {
// Form all the words of the
// form suffix{word and insert
// them in the trie
temp = "{" + words[i];
for (int j = words[i].size() - 1;
j >= 0; j--) {
t = words[i][j] + temp;
temp = t;
// Insert into Trie
insert(t, i);
}
}
// Traverse all the queries
for (int i = 0; i < Q.size(); i++) {
string prefix = Q[i][0];
string suffix = Q[i][1];
string temp = suffix + "{" + prefix;
// Stores the index of
// the required word
int res;
// Store the index of the
// word in the dictionary
res = search(temp);
// In case of match, print
// the corresponding string
if (res != -1) {
cout << words[res] << '\n';
}
// Otherwise, No match found
else
cout << "-1\n";
}
}
// Driver Code
int main()
{
string arr[]
= { "apple", "app", "biscuit",
"mouse", "orange", "bat",
"microphone", "mine" };
int N = 8;
vector<vector<string> > Q = { { "a", "e" }, { "mi", "ne" } };
findMatchingString(arr, N, Q);
return 0;
}
apple mine
Complejidad de Tiempo: O(N*M 2 + Q*M), donde M es la longitud máxima de entre todas las strings
Espacio Auxiliar: O(N*M 2 )