Dada una string ‘S’ que consta de corchetes abiertos y cerrados, la tarea es encontrar el número de formas en que cada carácter de ‘S’ se puede asignar a una string ‘X’ o string ‘Y’ (ambas inicialmente vacías) tales que las strings formadas por X e Y están balanceadas. Se puede suponer que ‘S’ está en sí misma equilibrada.
Ejemplos:
Input: S = "(())" Output: 6 Valid assignments are : X = "(())" and Y = "" [All characters in X] X = "" and Y = "(())" [Nothing in X] X = "()" and Y = "()" [1st and 3rd characters in X] X = "()" and Y = "()" [2nd and 3rd characters in X] X = "()" and Y = "()" [2nd and 4th characters in X] X = "()" and Y = "()" [1st and 4th characters in X] Input: S = "()()" Output: 4 X = "()()", Y = "" X = "()", Y = "()" [1st and 2nd in X] X = "()", Y = "" [1st and 4th in X] X = "", Y = "()()"
Un enfoque simple: podemos generar todas las formas posibles de asignar los caracteres y verificar si las strings formadas están balanceadas o no. Hay 2 n asignaciones, válidas o no válidas, y se necesita O(n) tiempo para verificar si las strings formadas están balanceadas o no. Por lo tanto, la complejidad temporal de este enfoque es O(n * 2 n ).
Un enfoque eficiente (programación dinámica): podemos resolver este problema de una manera más eficiente utilizando la programación dinámica. Podemos describir el estado actual de asignación utilizando tres variables: el índice i del carácter a asignar, y las strings formadas por X e Y hasta ese estado. Pasar las strings completas a las llamadas a funciones dará como resultado altos requisitos de memoria, por lo que podemos reemplazarlas con variables de conteo c xy c y . Incrementaremos la variable de conteo para cada paréntesis de apertura y la disminuiremos para cada paréntesis de cierre. La complejidad de tiempo y espacio de este enfoque es O(n 3 ).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of
// the above approach
#include <bits/stdc++.h>
using namespace std;
// For maximum length of input string
const int MAX = 10;
// Declaring the DP table
int F[MAX][MAX][MAX];
// Function to calculate the
// number of valid assignments
int noOfAssignments(string& S, int& n, int i,
int c_x, int c_y)
{
if (F[i][c_x][c_y] != -1)
return F[i][c_x][c_y];
if (i == n) {
// Return 1 if both
// subsequences are balanced
F[i][c_x][c_y] = !c_x && !c_y;
return F[i][c_x][c_y];
}
// Increment the count
// if it an opening bracket
if (S[i] == '(') {
F[i][c_x][c_y]
= noOfAssignments(S, n, i + 1,
c_x + 1, c_y)
+ noOfAssignments(S, n, i + 1,
c_x, c_y + 1);
return F[i][c_x][c_y];
}
F[i][c_x][c_y] = 0;
// Decrement the count
// if it a closing bracket
if (c_x)
F[i][c_x][c_y]
+= noOfAssignments(S, n, i + 1,
c_x - 1, c_y);
if (c_y)
F[i][c_x][c_y]
+= noOfAssignments(S, n, i + 1,
c_x, c_y - 1);
return F[i][c_x][c_y];
}
// Driver code
int main()
{
string S = "(())";
int n = S.length();
// Initializing the DP table
memset(F, -1, sizeof(F));
// Initial value for c_x
// and c_y is zero
cout << noOfAssignments(S, n, 0, 0, 0);
return 0;
}
Java
// Java implementation of the above approach
class GFG
{
// For maximum length of input string
static int MAX = 10;
// Declaring the DP table
static int[][][] F = new int[MAX][MAX][MAX];
// Function to calculate the
// number of valid assignments
static int noOfAssignments(String s, int n,
int i, int c_x, int c_y)
{
if (F[i][c_x][c_y] != -1)
return F[i][c_x][c_y];
if (i == n)
{
// Return 1 if both
// subsequences are balanced
F[i][c_x][c_y] = (c_x == 0 &&
c_y == 0) ? 1 : 0;
return F[i][c_x][c_y];
}
// Increment the count
// if it an opening bracket
if (s.charAt(i) == '(')
{
F[i][c_x][c_y] = noOfAssignments(s, n, i + 1,
c_x + 1, c_y) +
noOfAssignments(s, n, i + 1,
c_x, c_y + 1);
return F[i][c_x][c_y];
}
F[i][c_x][c_y] = 0;
// Decrement the count
// if it a closing bracket
if (c_x != 0)
F[i][c_x][c_y] += noOfAssignments(s, n, i + 1,
c_x - 1, c_y);
if (c_y != 0)
F[i][c_x][c_y] += noOfAssignments(s, n, i + 1,
c_x, c_y - 1);
return F[i][c_x][c_y];
}
// Driver Code
public static void main(String[] args)
{
String s = "(())";
int n = s.length();
// Initializing the DP table
for (int i = 0; i < MAX; i++)
for (int j = 0; j < MAX; j++)
for (int k = 0; k < MAX; k++)
F[i][j][k] = -1;
// Initial value for c_x
// and c_y is zero
System.out.println(noOfAssignments(s, n, 0, 0, 0));
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 implementation of above approach
# For maximum length of input string
MAX = 10
# Declaring the DP table
F = [[[-1 for i in range(MAX)]
for j in range(MAX)]
for k in range(MAX)]
# Function to calculate the number
# of valid assignments
def noOfAssignments(S, n, i, c_x, c_y):
if F[i][c_x][c_y] != -1:
return F[i][c_x][c_y]
if i == n:
# Return 1 if both subsequences are balanced
F[i][c_x][c_y] = not c_x and not c_y
return F[i][c_x][c_y]
# Increment the count if
# it is an opening bracket
if S[i] == '(':
F[i][c_x][c_y] = \
noOfAssignments(S, n, i + 1, c_x + 1, c_y) + \
noOfAssignments(S, n, i + 1, c_x, c_y + 1)
return F[i][c_x][c_y]
F[i][c_x][c_y] = 0
# Decrement the count
# if it a closing bracket
if c_x:
F[i][c_x][c_y] += \
noOfAssignments(S, n, i + 1, c_x - 1, c_y)
if c_y:
F[i][c_x][c_y] += \
noOfAssignments(S, n, i + 1, c_x, c_y - 1)
return F[i][c_x][c_y]
# Driver code
if __name__ == "__main__":
S = "(())"
n = len(S)
# Initial value for c_x and c_y is zero
print(noOfAssignments(S, n, 0, 0, 0))
# This code is contributed by Rituraj Jain
C#
// C# implementation of the above approach
using System;
class GFG
{
// For maximum length of input string
static int MAX = 10;
// Declaring the DP table
static int[,,] F = new int[MAX, MAX, MAX];
// Function to calculate the
// number of valid assignments
static int noOfAssignments(String s, int n,
int i, int c_x, int c_y)
{
if (F[i, c_x, c_y] != -1)
return F[i, c_x, c_y];
if (i == n)
{
// Return 1 if both
// subsequences are balanced
F[i, c_x, c_y] = (c_x == 0 &&
c_y == 0) ? 1 : 0;
return F[i, c_x, c_y];
}
// Increment the count
// if it an opening bracket
if (s[i] == '(')
{
F[i, c_x, c_y] = noOfAssignments(s, n, i + 1,
c_x + 1, c_y) +
noOfAssignments(s, n, i + 1,
c_x, c_y + 1);
return F[i, c_x, c_y];
}
F[i, c_x, c_y] = 0;
// Decrement the count
// if it a closing bracket
if (c_x != 0)
F[i, c_x, c_y] += noOfAssignments(s, n, i + 1,
c_x - 1, c_y);
if (c_y != 0)
F[i, c_x, c_y] += noOfAssignments(s, n, i + 1,
c_x, c_y - 1);
return F[i, c_x, c_y];
}
// Driver Code
public static void Main(String[] args)
{
String s = "(())";
int n = s.Length;
// Initializing the DP table
for (int i = 0; i < MAX; i++)
for (int j = 0; j < MAX; j++)
for (int k = 0; k < MAX; k++)
F[i, j, k] = -1;
// Initial value for c_x
// and c_y is zero
Console.WriteLine(noOfAssignments(s, n, 0, 0, 0));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript implementation of the above approach
// For maximum length of input string
let MAX = 10;
// Declaring the DP table
let F = new Array(MAX);
for(let i = 0; i < MAX; i++)
{
F[i] = new Array(MAX);
for(let j = 0; j < MAX; j++)
{
F[i][j] = new Array(MAX);
for(let k = 0; k < MAX; k++)
{
F[i][j][k] = -1;
}
}
}
// Function to calculate the
// number of valid assignments
function noOfAssignments(s,n,i,c_x,c_y)
{
if (F[i][c_x][c_y] != -1)
return F[i][c_x][c_y];
if (i == n)
{
// Return 1 if both
// subsequences are balanced
F[i][c_x][c_y] = (c_x == 0 &&
c_y == 0) ? 1 : 0;
return F[i][c_x][c_y];
}
// Increment the count
// if it an opening bracket
if (s.charAt(i) == '(')
{
F[i][c_x][c_y] = noOfAssignments(s, n, i + 1,
c_x + 1, c_y) +
noOfAssignments(s, n, i + 1,
c_x, c_y + 1);
return F[i][c_x][c_y];
}
F[i][c_x][c_y] = 0;
// Decrement the count
// if it a closing bracket
if (c_x != 0)
F[i][c_x][c_y] += noOfAssignments(s, n, i + 1,
c_x - 1, c_y);
if (c_y != 0)
F[i][c_x][c_y] += noOfAssignments(s, n, i + 1,
c_x, c_y - 1);
return F[i][c_x][c_y];
}
// Driver Code
let s = "(())";
let n = s.length;
// Initial value for c_x
// and c_y is zero
document.write(noOfAssignments(s, n, 0, 0, 0));
// This code is contributed by rag2127
</script>
Producción:
6
Enfoque de programación dinámica optimizada: podemos crear una array de prefijos para almacenar la variable de conteo c i para la substring S[0 : i + 1]. Podemos observar que la suma de c_x y c_y siempre será igual a la variable de conteo para toda la string. Al explotar esta propiedad, podemos reducir nuestro enfoque de programación dinámica a dos estados. Se puede crear una array de prefijos en complejidad lineal, por lo que la complejidad de tiempo y espacio de este enfoque es O(n 2 ).
C++
// C++ implementation of
// the above approach
#include <bits/stdc++.h>
using namespace std;
// For maximum length of input string
const int MAX = 10;
// Declaring the DP table
int F[MAX][MAX];
// Declaring the prefix array
int C[MAX];
// Function to calculate the
// number of valid assignments
int noOfAssignments(string& S, int& n,
int i, int c_x)
{
if (F[i][c_x] != -1)
return F[i][c_x];
if (i == n) {
// Return 1 if X is
// balanced.
F[i][c_x] = !c_x;
return F[i][c_x];
}
int c_y = C[i] - c_x;
// Increment the count
// if it an opening bracket
if (S[i] == '(') {
F[i][c_x]
= noOfAssignments(S, n, i + 1,
c_x + 1)
+ noOfAssignments(S, n,
i + 1, c_x);
return F[i][c_x];
}
F[i][c_x] = 0;
// Decrement the count
// if it a closing bracket
if (c_x)
F[i][c_x]
+= noOfAssignments(S, n,
i + 1, c_x - 1);
if (c_y)
F[i][c_x]
+= noOfAssignments(S, n,
i + 1, c_x);
return F[i][c_x];
}
// Driver code
int main()
{
string S = "()";
int n = S.length();
// Initializing the DP table
memset(F, -1, sizeof(F));
C[0] = 0;
// Creating the prefix array
for (int i = 0; i < n; ++i)
if (S[i] == '(')
C[i + 1] = C[i] + 1;
else
C[i + 1] = C[i] - 1;
// Initial value for c_x
// and c_y is zero
cout << noOfAssignments(S, n, 0, 0);
return 0;
}
Java
// Java implementation of the approach
public class GFG {
// For maximum length of input string
static int MAX = 10;
// Declaring the DP table
static int F[][] = new int[MAX][MAX];
// Declaring the prefix array
static int C[] = new int[MAX];
// Function to calculate the
// number of valid assignments
static int noOfAssignments(String S, int n, int i, int c_x) {
if (F[i][c_x] != -1) {
return F[i][c_x];
}
if (i == n) {
// Return 1 if X is
// balanced.
if (c_x == 1) {
F[i][c_x] = 0;
} else {
F[i][c_x] = 1;
}
return F[i][c_x];
}
int c_y = C[i] - c_x;
// Increment the count
// if it an opening bracket
if (S.charAt(i) == '(') {
F[i][c_x]
= noOfAssignments(S, n, i + 1,
c_x + 1)
+ noOfAssignments(S, n,
i + 1, c_x);
return F[i][c_x];
}
F[i][c_x] = 0;
// Decrement the count
// if it a closing bracket
if (c_x == 1) {
F[i][c_x]
+= noOfAssignments(S, n,
i + 1, c_x - 1);
}
if (c_y == 1) {
F[i][c_x]
+= noOfAssignments(S, n,
i + 1, c_x);
}
return F[i][c_x];
}
// Driver code
public static void main(String[] args) {
String S = "()";
int n = S.length();
// Initializing the DP table
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
F[i][j] = -1;
}
}
C[0] = 0;
// Creating the prefix array
for (int i = 0; i < n; ++i) {
if (S.charAt(i) == '(') {
C[i + 1] = C[i] + 1;
} else {
C[i + 1] = C[i] - 1;
}
}
// Initial value for c_x
// and c_y is zero
System.out.println(noOfAssignments(S, n, 0, 0));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of above approach
# For maximum length of input string
MAX = 10
# Declaring the DP table
F = [[-1 for i in range(MAX)]
for j in range(MAX)]
# Declaring the prefix array
C = [None] * MAX
# Function to calculate the
# number of valid assignments
def noOfAssignments(S, n, i, c_x):
if F[i][c_x] != -1:
return F[i][c_x]
if i == n:
# Return 1 if X is balanced.
F[i][c_x] = not c_x
return F[i][c_x]
c_y = C[i] - c_x
# Increment the count
# if it is an opening bracket
if S[i] == '(':
F[i][c_x] = \
noOfAssignments(S, n, i + 1, c_x + 1) + \
noOfAssignments(S, n, i + 1, c_x)
return F[i][c_x]
F[i][c_x] = 0
# Decrement the count if it is a closing bracket
if c_x:
F[i][c_x] += \
noOfAssignments(S, n, i + 1, c_x - 1)
if c_y:
F[i][c_x] += \
noOfAssignments(S, n, i + 1, c_x)
return F[i][c_x]
# Driver code
if __name__ == "__main__":
S = "()"
n = len(S)
C[0] = 0
# Creating the prefix array
for i in range(0, n):
if S[i] == '(':
C[i + 1] = C[i] + 1
else:
C[i + 1] = C[i] - 1
# Initial value for c_x and c_y is zero
print(noOfAssignments(S, n, 0, 0))
# This code is contributed by Rituraj Jain
C#
// C# implementation of the approach
using System;
public class GFG {
// For maximum length of input string
static int MAX = 10;
// Declaring the DP table
static int[,] F = new int[MAX,MAX];
// Declaring the prefix array
static int[] C = new int[MAX];
// Function to calculate the
// number of valid assignments
static int noOfAssignments(string S, int n, int i, int c_x) {
if (F[i,c_x] != -1) {
return F[i,c_x];
}
if (i == n) {
// Return 1 if X is
// balanced.
if (c_x == 1) {
F[i,c_x] = 0;
} else {
F[i,c_x] = 1;
}
return F[i,c_x];
}
int c_y = C[i] - c_x;
// Increment the count
// if it an opening bracket
if (S[i] == '(') {
F[i,c_x]
= noOfAssignments(S, n, i + 1,
c_x + 1)
+ noOfAssignments(S, n,
i + 1, c_x);
return F[i,c_x];
}
F[i,c_x] = 0;
// Decrement the count
// if it a closing bracket
if (c_x == 1) {
F[i,c_x]
+= noOfAssignments(S, n,
i + 1, c_x - 1);
}
if (c_y == 1) {
F[i,c_x]
+= noOfAssignments(S, n,
i + 1, c_x);
}
return F[i,c_x];
}
// Driver code
public static void Main() {
string S = "()";
int n = S.Length;
// Initializing the DP table
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
F[i,j] = -1;
}
}
C[0] = 0;
// Creating the prefix array
for (int i = 0; i < n; ++i) {
if (S[i] == '(') {
C[i + 1] = C[i] + 1;
} else {
C[i + 1] = C[i] - 1;
}
}
// Initial value for c_x
// and c_y is zero
Console.WriteLine(noOfAssignments(S, n, 0, 0));
}
}
// This code is contributed by Ita_c.
Javascript
<script>
// Javascript implementation of the approach
// For maximum length of input string
var MAX = 10;
// Declaring the DP table
var F = Array.from(Array(MAX), ()=>Array(MAX).fill(0));
// Declaring the prefix array
var C = Array(MAX).fill(0);
// Function to calculate the
// number of valid assignments
function noOfAssignments(S, n, i, c_x) {
if (F[i][c_x] != -1) {
return F[i][c_x];
}
if (i == n) {
// Return 1 if X is
// balanced.
if (c_x == 1) {
F[i][c_x] = 0;
} else {
F[i][c_x] = 1;
}
return F[i][c_x];
}
var c_y = C[i] - c_x;
// Increment the count
// if it an opening bracket
if (S[i] == '(') {
F[i][c_x]
= noOfAssignments(S, n, i + 1,
c_x + 1)
+ noOfAssignments(S, n,
i + 1, c_x);
return F[i][c_x];
}
F[i][c_x] = 0;
// Decrement the count
// if it a closing bracket
if (c_x == 1) {
F[i][c_x]
+= noOfAssignments(S, n,
i + 1, c_x - 1);
}
if (c_y == 1) {
F[i][c_x]
+= noOfAssignments(S, n,
i + 1, c_x);
}
return F[i][c_x];
}
// Driver code
var S = "()";
var n = S.length;
// Initializing the DP table
for(var i = 0; i < MAX; i++) {
for(var j = 0; j < MAX; j++) {
F[i][j] = -1;
}
}
C[0] = 0;
// Creating the prefix array
for (var i = 0; i < n; ++i) {
if (S[i] == '(') {
C[i + 1] = C[i] + 1;
} else {
C[i + 1] = C[i] - 1;
}
}
// Initial value for c_x
// and c_y is zero
document.write(noOfAssignments(S, n, 0, 0) + "<br>");
// This code is contributed by rrrtnx.
</script>
Producción:
2
Publicación traducida automáticamente
Artículo escrito por vaibhav29498 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA