Dada una string R(x) de longitud n que representa una expresión que tiene el conjunto de palabras bajo la gramática dada:
- Por cada letra minúscula x , R(x) = {x}
- Para expresiones e_1, e_2, …, e_k con k≥2 , R({e_1, e_2, …, e_k}) = R(e_1) ∪ R(e_2) ∪ … ∪ R(e_k) .
- Para las expresiones e_1 y e_2 , R(e_1 + e_2) = {a + b para (a, b) en R(e_1) × R(e_2)} , donde + denota concatenación y × denota el producto cartesiano.
La tarea es encontrar la lista ordenada de palabras que representa la expresión.
Ejemplos:
Entrada: “{{a, z}, a{b, c}, {ab, z}}”
Salida: [ “a”, “ab”, “ac”, “z” ]
Explicación: Cada palabra distinta se escribe una sola vez en la respuesta final.
{a, z}, a{b, c}, {ab, z} → {a, z}, {ab, ac}, {ab, z} → [a, z, ab, ac]Entrada: “{a, b}{c, {d, e}}”
Salida: [“ac”, “ad”, “ae”, “bc”, “bd”, “be”]
Enfoque: A partir de la gramática dada, las strings pueden representar un conjunto de palabras en minúsculas. Sea R(expr) el conjunto de palabras representado por la expresión. Considere los siguientes ejemplos para entender el enfoque.
- Las letras individuales representan un conjunto singleton que contiene esa palabra.
- Si se encuentra una lista delimitada por comas de 2 o más expresiones, tome la unión de posibilidades.
- Al concatenar dos expresiones, tome el conjunto de posibles concatenaciones entre dos palabras donde la primera palabra proviene de la primera expresión y la segunda palabra proviene de la segunda expresión.
R(“a”) = {“a”}
R(“w”) = {“w”}
R(“{a, b, c}”) = {“a”, “b”, “c”}
R(“{{a, b}, {b, c}}”) = {“a”, «b», «c»} (observe que el conjunto final solo contiene cada palabra como máximo una vez)
R(“{a, b}{c, d}”) = {“ac”, “ad”, “bc”, “bd”}
R(“a{b, c}{d, e}f{g , h}”) = {“abdfg”, “abdfh”, “abefg”, “abefh”, “acdfg”, “acdfh”, “acefg”, “acefh”}
Siga los pasos a continuación para resolver el problema:
- Itere sobre los caracteres de la string y verifique las siguientes tres condiciones:
- Si se encuentra {…} , obtenga el resultado dentro de {…} llamando recursivamente a la función y realice el producto cartesiano con el conjunto actual de strings con el conjunto de strings devuelto.
- Si se encuentra una coma (,) , inserte el conjunto actual de strings en el resultado y vacíe las strings actuales.
- Si se encuentra una letra, realice el producto cartesiano con el conjunto actual de strings.
- Finalmente, ordene todas las strings en el conjunto de resultados e imprima solo strings únicas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to get the Cartesian product
// of two set of strings
vector<string> getProduct(vector<string>& lhs,
vector<string>& rhs)
{
// If lhs is empty,
// return rhs
if (lhs.empty())
return rhs;
// Store the Cartesian product
// of two set of strings
vector<string> ret;
// Iterate over characters of both
// strings and insert Cartesian product
for (auto sl : lhs)
for (auto sr : rhs)
ret.push_back(sl + sr);
return ret;
}
// Function to find the sorted list of words
// that the expression represents
vector<string> braceExpansion(string expression)
{
// Store the sorted list of words
// that the expression represents
vector<string> ret;
// Store the current set of strings
vector<string> cur;
// Append Comma
expression += ', ';
// Stores the length of expression
int len = expression.size();
// Iterate over the characters
// of the string(expression)
for (int i = 0; i < len; ++i) {
// Stores the current character
char c = expression[i];
// If { is encountered, find
// its closing bracket, }
if (c == '{') {
// Store the characters inside
// of these brackets
string sub;
// Stores count of unbalanced '{''
int cnt = 1;
// Iterate over characters of
// expression after index i
while (++i < len) {
// If current character is '{'
if (expression[i] == '{') {
// Update cnt
++cnt;
}
// If current character is '}'
else if (expression[i] == '}') {
// Update cnt
--cnt;
}
// If cnt is equal to 0
if (cnt == 0)
break;
// Append current character
sub += expression[i];
}
// Recursively call the function
// for the string, sub
vector<string> sub_ret
= braceExpansion(sub);
// Store the cartesian product of cur
// and sub_ret in cur
cur = getProduct(cur, sub_ret);
}
// If current character is Comma
else if (c == ', ') {
// Push cur result into ret
ret.insert(begin(ret),
begin(cur), end(cur));
// Clear the current set
// of strings
cur.clear();
}
else {
// Append the current character to tmp
vector<string> tmp(1, string(1, c));
// Store the cartesian product of
// tmp and cur in cur
cur = getProduct(cur, tmp);
}
}
// Sort the strings present in ret
// and get only the unique set of strings
sort(begin(ret), end(ret));
auto iter = unique(begin(ret), end(ret));
ret.resize(distance(begin(ret), iter));
return ret;
}
// Driver Code
int main()
{
// Given expression, str
string str = "{a, b}{c, {d, e}}";
// Store the sorted list of words
vector<string> res;
// Function Call
res = braceExpansion(str);
// Print the sorted list of words
for (string x : res) {
cout << x << " ";
}
return 0;
}
ac ad ae bc bd be
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rohit2sahu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA