Dadas N secuencias de corchetes, la tarea es encontrar el número de pares de secuencias de corchetes mediante la unión de los cuales se puede obtener una secuencia de corchetes equilibrada como un todo. Una secuencia de corchetes entre paréntesis solo puede ser parte de un solo par.
Ejemplos:
Input: { ")())", ")", "((", "((", "(", ")", ")"} Output: 2 Bracket sequence {1, 3} and {5, 6} Input: {"()", "(())", "(())", "()"} Output: 2 Since all brackets are balanced, hence we can form 2 pairs with 4.
Enfoque: Se pueden seguir los siguientes pasos para resolver el problema anterior:
- Cuente los corchetes de apertura y cierre requeridos, de individuos.
- Si los paréntesis de cierre requeridos son > 0 y los paréntesis de apertura son 0, entonces haga un hash del número de cierre requerido del paréntesis.
- De manera similar, si los paréntesis de apertura requeridos son > 0 y los corchetes de cierre son 0, entonces haga un hash del número de apertura requerido del paréntesis.
- Cuente las secuencias de paréntesis equilibrados.
- Agregue (número de secuencias de paréntesis equilibradas/2) al número de pares.
- Por cada número de secuencias que requiera el mismo número de paréntesis de apertura, min(hash[abrir], hash[cerrar]) se agregará al número de pares
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count the number of pairs // of balanced parentheses #include <bits/stdc++.h> using namespace std; // Function to count the number of pairs int countPairs(string bracks[], int num) { // Hashing function to count the // opening and closing brackets unordered_map<int, int> open, close; int cnt = 0; // Traverse for all bracket sequences for (int i = 0; i < num; i++) { // Get the string string s = bracks[i]; int l = s.length(); // Counts the opening and closing required int op = 0, cl = 0; // Traverse in the string for (int j = 0; j < l; j++) { // If it is a opening bracket if (s[j] == '(') op++; else // Closing bracket { // If openings are there, then close it if (op) op--; else // Else increase count of closing cl++; } } // If requirements of openings // are there and no closing if (op && !cl) open[op]++; // If requirements of closing // are there and no opening if (cl && !op) close[cl]++; // Perfect if (!op && !cl) cnt++; } // Divide by two since two // perfect makes one pair cnt = cnt / 2; // Traverse in the open and find // corresponding minimum for (auto it : open) cnt += min(it.second, close[it.first]); return cnt; } // Driver Code int main() { string bracks[] = { ")())", ")", "((", "((", "(", ")", ")" }; int num = sizeof(bracks) / sizeof(bracks[0]); cout << countPairs(bracks, num); }
Java
// Java program to count the number of pairs // of balanced parentheses import java.util.HashMap; class GFG { // Function to count the number of pairs static int countPairs(String[] bracks, int num) { // Hashing function to count the // opening and closing brackets HashMap<Integer, Integer> open = new HashMap<>(); HashMap<Integer, Integer> close = new HashMap<>(); int cnt = 0; // Traverse for all bracket sequences for (int i = 0; i < num; i++) { // Get the string String s = bracks[i]; int l = s.length(); // Counts the opening and closing required int op = 0, cl = 0; // Traverse in the string for (int j = 0; j < l; j++) { // If it is a opening bracket if (s.charAt(j) == '(') op++; // Closing bracket else { // If openings are there, then close it if (op != 0) op--; // Else increase count of closing else cl++; } } // If requirements of openings // are there and no closing if (op != 0 && cl == 0) open.put(op, open.get(op) == null ? 1 : open.get(op) + 1); // If requirements of closing // are there and no opening if (cl != 0 && op == 0) close.put(cl, close.get(cl) == null ? 1 : close.get(cl) + 1); // Perfect if (op == 0 && cl == 0) cnt++; } // Divide by two since two // perfect makes one pair cnt /= 2; // Traverse in the open and find // corresponding minimum for (HashMap.Entry<Integer, Integer> it : open.entrySet()) cnt += Math.min(it.getValue(), close.get(it.getKey())); return cnt; } // Driver Code public static void main(String[] args) { String[] bracks = { ")())", ")", "((", "((", "(", ")", ")" }; int num = bracks.length; System.out.println(countPairs(bracks, num)); } } // This code is contributed by // sanjeev2552
Python3
# Python3 program to count the number of pairs # of balanced parentheses import math as mt # Function to count the number of pairs def countPairs(bracks, num): # Hashing function to count the # opening and closing brackets openn=dict() close=dict() cnt = 0 # Traverse for all bracket sequences for i in range(num): # Get the string s = bracks[i] l = len(s) # Counts the opening and closing required op,cl = 0,0 # Traverse in the string for j in range(l): # If it is a opening bracket if (s[j] == '('): op+=1 else: # Closing bracket # If openings are there, then close it if (op): op-=1 else: # Else increase count of closing cl+=1 # If requirements of openings # are there and no closing if (op and cl==0): if op in openn.keys(): openn[op]+=1 else: openn[op]=1 # If requirements of closing # are there and no opening if (cl and op==0): if cl in openn.keys(): close[cl]+=1 else: close[cl]=1 # Perfect if (op==0 and cl==0): cnt+=1 # Divide by two since two # perfect makes one pair cnt = cnt //2 # Traverse in the open and find # corresponding minimum for it in openn: cnt += min(openn[it], close[it]) return cnt # Driver Code bracks= [")())", ")", "((", "((", "(", ")", ")" ] num = len(bracks) print(countPairs(bracks, num)) #This code is contributed by Mohit kumar 29
C#
// C# program to count the number of pairs // of balanced parentheses using System; using System.Collections.Generic; class GFG{ // Function to count the number of pairs static int countPairs(string[] bracks, int num) { // Hashing function to count the // opening and closing brackets Dictionary<int, int> open = new Dictionary<int, int>(); Dictionary<int, int> close = new Dictionary<int, int>(); int cnt = 0; // Traverse for all bracket sequences for(int i = 0; i < num; i++) { // Get the string string s = bracks[i]; int l = s.Length; // Counts the opening and closing required int op = 0, cl = 0; // Traverse in the string for(int j = 0; j < l; j++) { // If it is a opening bracket if (s[j] == '(') op++; // Closing bracket else { // If openings are there, then close it if (op != 0) op--; // Else increase count of closing else cl++; } } // If requirements of openings // are there and no closing if (op != 0 && cl == 0) { if (open.ContainsKey(op)) { open[op]++; } else { open[op] = 1; } } // If requirements of closing // are there and no opening if (cl != 0 && op == 0) { if (close.ContainsKey(cl)) { close[cl]++; } else { close[cl] = 1; } } // Perfect if (op == 0 && cl == 0) cnt++; } // Divide by two since two // perfect makes one pair cnt /= 2; // Traverse in the open and find // corresponding minimum foreach(KeyValuePair<int, int> it in open) { cnt += Math.Min(it.Value, close[it.Value]); } return cnt; } // Driver Code public static void Main(string[] args) { string[] bracks = { ")())", ")", "((", "((", "(", ")", ")" }; int num = bracks.Length; Console.Write(countPairs(bracks, num)); } } // This code is contributed by rutvik_56
Javascript
<script> // Javascript program to count the number of pairs // of balanced parentheses // Function to count the number of pairs function countPairs( bracks,num) { // Hashing function to count the // opening and closing brackets let open = new Map(); let close = new Map(); let cnt = 0; // Traverse for all bracket sequences for (let i = 0; i < num; i++) { // Get the string let s = bracks[i]; let l = s.length; // Counts the opening and closing required let op = 0, cl = 0; // Traverse in the string for (let j = 0; j < l; j++) { // If it is a opening bracket if (s[j] == '(') op++; // Closing bracket else { // If openings are there, then close it if (op != 0) op--; // Else increase count of closing else cl++; } } // If requirements of openings // are there and no closing if (op != 0 && cl == 0) open.set(op, open.get(op) == null ? 1 : open.get(op) + 1); // If requirements of closing // are there and no opening if (cl != 0 && op == 0) close.set(cl, close.get(cl) == null ? 1 : close.get(cl) + 1); // Perfect if (op == 0 && cl == 0) cnt++; } // Divide by two since two // perfect makes one pair cnt /= 2; // Traverse in the open and find // corresponding minimum for (let [key, value] of open.entries()) cnt += Math.min(value, close.get(value)); return cnt; } // Driver Code let bracks=[")())", ")", "((", "((", "(", ")", ")"]; let num = bracks.length; document.write(countPairs(bracks, num)); // This code is contributed by patel2127 </script>
2
Complejidad de tiempo: O(N*M), ya que estamos usando bucles anidados para atravesar N*M veces. Donde N es el número de strings en los corchetes y M es la longitud máxima de las strings presentes en los corchetes.
Espacio auxiliar: O(N), ya que estamos usando espacio extra para el mapa. Donde N es el número de strings entre corchetes.