Dada una secuencia de paréntesis desequilibrada como una string str , la tarea es encontrar si la string dada se puede equilibrar moviendo como máximo un paréntesis de su lugar original en la secuencia a cualquier otra posición.
Ejemplos:
Entrada: str = “)(()”
Salida: Sí
Como mover s[0] al final lo hará válido.
“(())”
Entrada: str = “()))(()”
Salida: No
Enfoque: Considere X como un corchete válido, entonces definitivamente (X) también es válido. Si X no es válido y se puede equilibrar con un solo cambio de posición en algún paréntesis, entonces debe ser del tipo X = “)(“ donde ‘)’ se ha colocado antes de ‘(‘ .
Ahora, X se puede reemplazar con ( X) ya que no afectará la naturaleza balanceada de X. La nueva string se convierte en X = «()()» que está balanceada.
Por lo tanto, si (X) está balanceada, entonces podemos decir que X puede balancearse como máximo con una cambio en la posición de algún soporte.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP implementation of the approach #include <bits/stdc++.h> using namespace std; // Function that returns true if the sequence // can be balanced by changing the // position of at most one bracket bool canBeBalanced(string s, int n) { // Odd length string can // never be balanced if (n % 2 == 1) return false; // Add '(' in the beginning and ')' // in the end of the string string k = "("; k += s + ")"; vector<string> d; int cnt = 0; for (int i = 0; i < k.length(); i++) { // If its an opening bracket then // append it to the temp string if (k[i] == '(') d.push_back("("); // If its a closing bracket else { // There was an opening bracket // to match it with if (d.size() != 0) d.pop_back(); // No opening bracket to // match it with else return false; } } // Sequence is balanced if (d.empty()) return true; return false; } // Driver Code int main(int argc, char const *argv[]) { string s = ")(()"; int n = s.length(); (canBeBalanced(s, n)) ? cout << "Yes" << endl : cout << "No" << endl; return 0; } // This code is contributed by // sanjeev2552
Java
// Java implementation of the approach import java.util.Vector; class GFG { // Function that returns true if the sequence // can be balanced by changing the // position of at most one bracket static boolean canBeBalanced(String s, int n) { // Odd length string can // never be balanced if (n % 2 == 1) return false; // Add '(' in the beginning and ')' // in the end of the string String k = "("; k += s + ")"; Vector<String> d = new Vector<>(); for (int i = 0; i < k.length(); i++) { // If its an opening bracket then // append it to the temp string if (k.charAt(i) == '(') d.add("("); // If its a closing bracket else { // There was an opening bracket // to match it with if (d.size() != 0) d.remove(d.size() - 1); // No opening bracket to // match it with else return false; } } // Sequence is balanced if (d.isEmpty()) return true; return false; } // Driver Code public static void main(String[] args) { String s = ")(()"; int n = s.length(); if (canBeBalanced(s, n)) System.out.println("Yes"); else System.out.println("No"); } } // This code is contributed by // sanjeev2552
Python3
# Python3 implementation of the approach # Function that returns true if the sequence # can be balanced by changing the # position of at most one bracket def canBeBalanced(s, n): # Odd length string can # never be balanced if n % 2 == 1: return False # Add '(' in the beginning and ')' # in the end of the string k = "(" k = k + s+")" d = [] count = 0 for i in range(len(k)): # If its an opening bracket then # append it to the temp string if k[i] == "(": d.append("(") # If its a closing bracket else: # There was an opening bracket # to match it with if len(d)!= 0: d.pop() # No opening bracket to # match it with else: return False # Sequence is balanced if len(d) == 0: return True return False # Driver code S = ")(()" n = len(S) if(canBeBalanced(S, n)): print("Yes") else: print("No")
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { // Function that returns true if the sequence // can be balanced by changing the // position of at most one bracket static bool canBeBalanced(string s, int n) { // Odd length string can // never be balanced if (n % 2 == 1) return false; // Add '(' in the beginning and ')' // in the end of the string string k = "("; k += s + ")"; List<string> d = new List<string>(); for (int i = 0; i < k.Length; i++) { // If its an opening bracket then // append it to the temp string if (k[i] == '(') d.Add("("); // If its a closing bracket else { // There was an opening bracket // to match it with if (d.Count != 0) d.RemoveAt(d.Count - 1); // No opening bracket to // match it with else return false; } } // Sequence is balanced if (d.Count == 0) return true; return false; } // Driver Code public static void Main() { string s = ")(()"; int n = s.Length; if (canBeBalanced(s, n)) Console.Write("Yes"); else Console.Write("No"); } } // This code is contributed by // mohit kumar 29
Javascript
<script> // JavaScript implementation of the approach // Function that returns true if the sequence // can be balanced by changing the // position of at most one bracket function canBeBalanced(s,n) { // Odd length string can // never be balanced if (n % 2 == 1) return false; // Add '(' in the beginning and ')' // in the end of the string let k = "("; k += s + ")"; let d = []; for (let i = 0; i < k.length; i++) { // If its an opening bracket then // append it to the temp string if (k[i] == '(') d.push("("); // If its a closing bracket else { // There was an opening bracket // to match it with if (d.length != 0) d.pop(); // No opening bracket to // match it with else return false; } } // Sequence is balanced if (d.length==0) return true; return false; } // Driver Code let s = ")(()"; let n = s.length; if (canBeBalanced(s, n)) document.write("Yes"); else document.write("No"); // This code is contributed by unknown2108 </script>
Yes
Complejidad de tiempo: O (n), donde n es el tamaño de la string dada
Complejidad espacial : O(n)
Publicación traducida automáticamente
Artículo escrito por divyamohan123 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA