Dada una array arr[] que consta de N strings donde cada string consta de ‘(‘ y ‘)’ , la tarea es comprobar si se puede formar una secuencia de paréntesis regular con la concatenación de las strings dadas o no. Si se encuentra que es cierto, escriba Sí . De lo contrario , imprima No.
Ejemplos:
Entrada: arr[] = { “)”, “()(” }
Salida: Sí
Explicación: La string válida es S[1] + S[0] = “()()”.Entrada: arr[] = { “)(“, “()”}
Salida: No
Explicación: No son posibles secuencias de paréntesis regulares válidas.
Enfoque: el problema dado se puede resolver con la ayuda del enfoque codicioso, que se basa en las siguientes observaciones:
- Si una string contiene un par de letras consecutivas ‘(‘ y ‘)’ , eliminar esas dos letras no afecta el resultado.
- Al repetir esta operación, cada S[i] se convierte en una string (posiblemente vacía) que consta de 0 o más repeticiones de ‘)’, seguidas de 0 o más repeticiones de ‘(‘ .
- Entonces cada string se puede denotar con dos variables A[i] = el número de ‘)’, y B[i] = el número de ‘(‘ .
- Mantenga un par vector r v[][] para almacenar estos valores.
- Ahora, separe las dos strings en dos vectores separados pos[] y neg[] .
- pos[] almacenará aquellas strings en las que la suma total sea positiva y neg[] almacenará strings cuya suma total sea negativa .
- Ahora, la forma óptima es concatenar strings positivas primero y luego strings negativas en orden creciente.
Siga los pasos a continuación para resolver el problema:
- Mantenga un vector de par v[][] que almacenará los valores {suma, prefijo mínimo} , donde la suma se calcula por +1 para ‘(‘ y -1 para ‘)’ y el prefijo mínimo es el máximo consecutivo ‘) ‘ en la string.
- Iterar sobre el rango [0. N) utilizando la variable i y realizar los siguientes pasos:
- Inicialice 2 variables sum y pre como 0 para almacenar la suma y el prefijo mínimo para la string dada.
- Itere sobre el rango [0, M) para cada carácter de la string, y si el carácter actual es ‘(‘, entonces incremente la suma en 1 ; de lo contrario, disminúyala en 1 y establezca el valor de pre como el mínimo de pre o suma en cada paso.
- Establezca el valor de v[ I ] como { sum, pre }.
- Iterar sobre el rango [0. N) para los elementos en v[] y para cada par si la suma es positiva, almacene el valor {-min_prefix, sum} en pos[] vector; de lo contrario , {sum – min_prefix, -sum} en neg[] vector .
- Ordena estos vectores en orden creciente .
- Inicialice la variable open como 0 .
- Iterar sobre el rango [0. size) donde size es el tamaño del vector pos[] usando la variable de iterador p y si está abierto – p.first es mayor que igual a 0 luego agregue p.second a la variable open . De lo contrario, imprima No y regrese.
- Inicialice la variable negativa como 0 .
- Iterar sobre el rango [0. size) donde size es el tamaño del vector neg[] usando la variable iteradora p y si es negativo – p.first es mayor que igual a 0 luego agregue p.second a la variable negativa . De lo contrario, imprima No y regrese.
- Si el valor de abierto no es igual a negativo , imprima No. De lo contrario, imprima Sí .
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;
// Function to check possible RBS from
// the given strings
int checkRBS(vector<string> S)
{
int N = S.size();
// Stores the values {sum, min_prefix}
vector<pair<int, int> > v(N);
// Iterate over the range
for (int i = 0; i < N; ++i) {
string s = S[i];
// Stores the total sum
int sum = 0;
// Stores the minimum prefix
int pre = 0;
for (char c : s) {
if (c == '(') {
++sum;
}
else {
--sum;
}
// Check for minimum prefix
pre = min(sum, pre);
}
// Store these values in vector
v[i] = { sum, pre };
}
// Make two pair vectors pos and neg
vector<pair<int, int> > pos;
vector<pair<int, int> > neg;
// Store values according to the
// mentioned approach
for (int i = 0; i < N; ++i) {
if (v[i].first >= 0) {
pos.push_back(
{ -v[i].second, v[i].first });
}
else {
neg.push_back(
{ v[i].first - v[i].second,
-v[i].first });
}
}
// Sort the positive vector
sort(pos.begin(), pos.end());
// Stores the extra count of
// open brackets
int open = 0;
for (auto p : pos) {
if (open - p.first >= 0) {
open += p.second;
}
// No valid bracket sequence
// can be formed
else {
cout << "No"
<< "\n";
return 0;
}
}
// Sort the negative vector
sort(neg.begin(), neg.end());
// Stores the count of the
// negative elements
int negative = 0;
for (auto p : neg) {
if (negative - p.first >= 0) {
negative += p.second;
}
// No valid bracket sequence
// can be formed
else {
cout << "No\n";
return 0;
}
}
// Check if open is equal to negative
if (open != negative) {
cout << "No\n";
return 0;
}
cout << "Yes\n";
return 0;
}
// Driver Code
int main()
{
vector<string> arr = { ")", "()(" };
checkRBS(arr);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to check possible RBS from
// the given Strings
static int checkRBS(String[] S)
{
int N = S.length;
// Stores the values {sum, min_prefix}
pair []v = new pair[N];
// Iterate over the range
for (int i = 0; i < N; ++i) {
String s = S[i];
// Stores the total sum
int sum = 0;
// Stores the minimum prefix
int pre = 0;
for (char c : s.toCharArray()) {
if (c == '(') {
++sum;
}
else {
--sum;
}
// Check for minimum prefix
pre = Math.min(sum, pre);
}
// Store these values in vector
v[i] = new pair( sum, pre );
}
// Make two pair vectors pos and neg
Vector<pair> pos = new Vector<pair>();
Vector<pair > neg = new Vector<pair>();
// Store values according to the
// mentioned approach
for (int i = 0; i < N; ++i) {
if (v[i].first >= 0) {
pos.add(
new pair( -v[i].second, v[i].first ));
}
else {
neg.add(
new pair( v[i].first - v[i].second,
-v[i].first ));
}
}
// Sort the positive vector
Collections.sort(pos,(a,b)->a.first-b.first);
// Stores the extra count of
// open brackets
int open = 0;
for (pair p : pos) {
if (open - p.first >= 0) {
open += p.second;
}
// No valid bracket sequence
// can be formed
else {
System.out.print("No"
+ "\n");
return 0;
}
}
// Sort the negative vector
Collections.sort(neg,(a,b)->a.first-b.first);
// Stores the count of the
// negative elements
int negative = 0;
for (pair p : neg) {
if (negative - p.first >= 0) {
negative += p.second;
}
// No valid bracket sequence
// can be formed
else {
System.out.print("No\n");
return 0;
}
}
// Check if open is equal to negative
if (open != negative) {
System.out.print("No\n");
return 0;
}
System.out.print("Yes\n");
return 0;
}
// Driver Code
public static void main(String[] args)
{
String []arr = { ")", "()(" };
checkRBS(arr);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python 3 program for the above approach
# Function to check possible RBS from
# the given strings
def checkRBS(S):
N = len(S)
# Stores the values {sum, min_prefix}
v = [0]*(N)
# Iterate over the range
for i in range(N):
s = S[i]
# Stores the total sum
sum = 0
# Stores the minimum prefix
pre = 0
for c in s:
if (c == '('):
sum += 1
else:
sum -= 1
# Check for minimum prefix
pre = min(sum, pre)
# Store these values in vector
v[i] = [sum, pre]
pos = []
neg = []
# Store values according to the
# mentioned approach
for i in range(N):
if (v[i][0] >= 0):
pos.append(
[-v[i][1], v[i][0]])
else:
neg.append(
[v[i][0] - v[i][1],
-v[i][0]])
# Sort the positive vector
pos.sort()
# Stores the extra count of
# open brackets
open = 0
for p in pos:
if (open - p[0] >= 0):
open += p[1]
# No valid bracket sequence
# can be formed
else:
print("No")
return 0
# Sort the negative vector
neg.sort()
# Stores the count of the
# negative elements
negative = 0
for p in neg:
if (negative - p[0] >= 0):
negative += p[1]
# No valid bracket sequence
# can be formed
else:
print("No")
return 0
# Check if open is equal to negative
if (open != negative):
print("No")
return 0
print("Yes")
# Driver Code
if __name__ == "__main__":
arr = [")", "()("]
checkRBS(arr)
# This code is contributed by ukasp.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG{
class pair : IComparable<pair>
{
public int first,second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
public int CompareTo(pair p)
{
return this.first - p.first;
}
}
// Function to check possible RBS from
// the given Strings
static int checkRBS(String[] S)
{
int N = S.Length;
// Stores the values {sum, min_prefix}
pair []v = new pair[N];
// Iterate over the range
for (int i = 0; i < N; ++i) {
String s = S[i];
// Stores the total sum
int sum = 0;
// Stores the minimum prefix
int pre = 0;
foreach (char c in s.ToCharArray()) {
if (c == '(') {
++sum;
}
else {
--sum;
}
// Check for minimum prefix
pre = Math.Min(sum, pre);
}
// Store these values in vector
v[i] = new pair( sum, pre );
}
// Make two pair vectors pos and neg
List<pair> pos = new List<pair>();
List<pair > neg = new List<pair>();
// Store values according to the
// mentioned approach
for (int i = 0; i < N; ++i) {
if (v[i].first >= 0) {
pos.Add(
new pair( -v[i].second, v[i].first ));
}
else {
neg.Add(
new pair( v[i].first - v[i].second,
-v[i].first ));
}
}
// Sort the positive vector
pos.Sort();
// Stores the extra count of
// open brackets
int open = 0;
foreach (pair p in pos) {
if (open - p.first >= 0) {
open += p.second;
}
// No valid bracket sequence
// can be formed
else {
Console.Write("No"
+ "\n");
return 0;
}
}
// Sort the negative vector
neg.Sort();
// Stores the count of the
// negative elements
int negative = 0;
foreach (pair p in neg) {
if (negative - p.first >= 0) {
negative += p.second;
}
// No valid bracket sequence
// can be formed
else {
Console.Write("No\n");
return 0;
}
}
// Check if open is equal to negative
if (open != negative) {
Console.Write("No\n");
return 0;
}
Console.Write("Yes\n");
return 0;
}
// Driver Code
public static void Main(String[] args)
{
String []arr = { ")", "()(" };
checkRBS(arr);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
// Function to check possible RBS from
// the given strings
function checkRBS(S) {
let N = S.length;
// Stores the values {sum, min_prefix}
let v = new Array(N);
// Iterate over the range
for (let i = 0; i < N; ++i) {
let s = S[i];
// Stores the total sum
let sum = 0;
// Stores the minimum prefix
let pre = 0;
for (let c of s) {
if (c == "(") {
++sum;
} else {
--sum;
}
// Check for minimum prefix
pre = Math.min(sum, pre);
}
// Store these values in vector
v[i] = [sum, pre];
}
// Make two pair vectors pos and neg
let pos = [];
let neg = [];
// Store values according to the
// mentioned approach
for (let i = 0; i < N; ++i) {
if (v[i][0] >= 0) {
pos.push([-v[i][1], v[i][0]]);
} else {
neg.push([v[i][0] - v[i][1], -v[i][0]]);
}
}
// Sort the positive vector
pos.sort((a, b) => a - b);
// Stores the extra count of
// open brackets
let open = 0;
for (let p of pos) {
if (open - p[0] >= 0) {
open += p[1];
}
// No valid bracket sequence
// can be formed
else {
document.write("No" + "<br>");
return 0;
}
}
// Sort the negative vector
neg.sort((a, b) => a - b);
// Stores the count of the
// negative elements
let negative = 0;
for (let p of neg) {
if (negative - p[0] >= 0) {
negative += p[1];
}
// No valid bracket sequence
// can be formed
else {
document.write("No<br>");
return 0;
}
}
// Check if open is equal to negative
if (open != negative) {
document.write("No<br>");
return 0;
}
document.write("Yes<br>");
return 0;
}
// Driver Code
let arr = [")", "()("];
checkRBS(arr);
// This code is contributed by gfgking.
</script>
Producción:
Yes
Complejidad de tiempo: O(N*M + N*log(N)), donde M es la longitud máxima de la string en la array arr[].
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA