Número de formas de dividir una string en dos subsecuencias equilibradas

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *