Dado un número entero N , la tarea es generar todas las strings binarias posibles de longitud N que contengan «01» como substring exactamente dos veces.
Ejemplos:
Entrada: N = 4
Salida:
0101
“0101” es la única string binaria de longitud 4
que contiene “01” exactamente el doble que la substring.Entrada: N = 5
Salida:
00101
01001
01010
01011
01101
10101
Enfoque: Este problema se puede resolver usando backtracking . Para generar una string binaria, implementamos una función que genera cada bit a la vez, actualiza el estado de la string binaria (longitud actual, número de ocurrencias del patrón). Luego llame a la función de forma recursiva y, de acuerdo con el estado actual de la string binaria, la función decidirá cómo generar el siguiente bit o imprimir la string binaria (si se cumple el requisito del problema).
Para este problema, la estrategia de retroceso parece que generamos un árbol binario con cada Node que puede tener el valor 0 o 1 .
Por ejemplo, con N = 4 , el árbol se verá así:
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <iostream>
#include <stdlib.h>
using namespace std;
// Utility function to print the given binary string
void printBinStr(int* str, int len)
{
for (int i = 0; i < len; i++) {
cout << str[i];
}
cout << endl;
}
// This function will be called recursively
// to generate the next bit for given
// binary string according to its current state
void generateBinStr(int* str, int len, int currlen,
int occur, int nextbit)
{
// Base-case: if the generated binary string
// meets the required length and the pattern "01"
// appears twice
if (currlen == len) {
// nextbit needs to be 0 because each time
// we call the function recursively,
// we call 2 times for 2 cases:
// next bit is 0 or 1
// The is to assure that the binary
// string is printed one time only
if (occur == 2 && nextbit == 0)
printBinStr(str, len);
return;
}
// Generate the next bit for str
// and call recursive
if (currlen == 0) {
// Assign first bit
str[0] = nextbit;
// The next generated bit will wither be 0 or 1
generateBinStr(str, len, currlen + 1, occur, 0);
generateBinStr(str, len, currlen + 1, occur, 1);
}
else {
// If pattern "01" occurrence is < 2
if (occur < 2) {
// Set next bit
str[currlen] = nextbit;
// If pattern "01" appears then
// increase the occurrence of pattern
if (str[currlen - 1] == 0 && nextbit == 1) {
occur += 1;
}
generateBinStr(str, len, currlen + 1, occur, 0);
generateBinStr(str, len, currlen + 1, occur, 1);
// Else pattern "01" occurrence equals 2
}
else {
// If previous bit is 0 then next bit cannot be 1
if (str[currlen - 1] == 0 && nextbit == 1) {
return;
// Otherwise
}
else {
str[currlen] = nextbit;
generateBinStr(str, len, currlen + 1, occur, 0);
generateBinStr(str, len, currlen + 1, occur, 1);
}
}
}
}
// Driver code
int main()
{
int n = 5;
// Length of the resulting strings
// must be at least 4
if (n < 4)
cout << -1;
else {
int* str = new int[n];
// Generate all binary strings of length n
// with sub-string "01" appearing twice
generateBinStr(str, n, 0, 0, 0);
generateBinStr(str, n, 0, 0, 1);
}
return 0;
}
Java
// Java implementation of the above approach
class GFG
{
// Utility function to print the given binary string
static void printBinStr(int[] str, int len)
{
for (int i = 0; i < len; i++)
{
System.out.print(str[i]);
}
System.out.println();
}
// This function will be called recursively
// to generate the next bit for given
// binary string according to its current state
static void generateBinStr(int[] str, int len, int currlen,
int occur, int nextbit)
{
// Base-case: if the generated binary string
// meets the required length and the pattern "01"
// appears twice
if (currlen == len)
{
// nextbit needs to be 0 because each time
// we call the function recursively,
// we call 2 times for 2 cases:
// next bit is 0 or 1
// The is to assure that the binary
// string is printed one time only
if (occur == 2 && nextbit == 0)
{
printBinStr(str, len);
}
return;
}
// Generate the next bit for str
// and call recursive
if (currlen == 0)
{
// Assign first bit
str[0] = nextbit;
// The next generated bit will wither be 0 or 1
generateBinStr(str, len, currlen + 1, occur, 0);
generateBinStr(str, len, currlen + 1, occur, 1);
} else // If pattern "01" occurrence is < 2
if (occur < 2)
{
// Set next bit
str[currlen] = nextbit;
// If pattern "01" appears then
// increase the occurrence of pattern
if (str[currlen - 1] == 0 && nextbit == 1)
{
occur += 1;
}
generateBinStr(str, len, currlen + 1, occur, 0);
generateBinStr(str, len, currlen + 1, occur, 1);
// Else pattern "01" occurrence equals 2
} else // If previous bit is 0 then next bit cannot be 1
if (str[currlen - 1] == 0 && nextbit == 1)
{
return;
// Otherwise
}
else
{
str[currlen] = nextbit;
generateBinStr(str, len, currlen + 1, occur, 0);
generateBinStr(str, len, currlen + 1, occur, 1);
}
}
// Driver code
public static void main(String[] args)
{
int n = 5;
// Length of the resulting strings
// must be at least 4
if (n < 4)
{
System.out.print(-1);
}
else
{
int[] str = new int[n];
// Generate all binary strings of length n
// with sub-string "01" appearing twice
generateBinStr(str, n, 0, 0, 0);
generateBinStr(str, n, 0, 0, 1);
}
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python3 implementation of the approach # Utility function to print the # given binary string def printBinStr(string, length): for i in range(0, length): print(string[i], end = "") print() # This function will be called recursively # to generate the next bit for given # binary string according to its current state def generateBinStr(string, length, currlen, occur, nextbit): # Base-case: if the generated binary # string meets the required length and # the pattern "01" appears twice if currlen == length: # nextbit needs to be 0 because each # time we call the function recursively, # we call 2 times for 2 cases: # next bit is 0 or 1 # The is to assure that the binary # string is printed one time only if occur == 2 and nextbit == 0: printBinStr(string, length) return # Generate the next bit for # str and call recursive if currlen == 0: # Assign first bit string[0] = nextbit # The next generated bit will # either be 0 or 1 generateBinStr(string, length, currlen + 1, occur, 0) generateBinStr(string, length, currlen + 1, occur, 1) else: # If pattern "01" occurrence is < 2 if occur < 2: # Set next bit string[currlen] = nextbit # If pattern "01" appears then # increase the occurrence of pattern if string[currlen - 1] == 0 and nextbit == 1: occur += 1 generateBinStr(string, length, currlen + 1, occur, 0) generateBinStr(string, length, currlen + 1, occur, 1) # Else pattern "01" occurrence equals 2 else: # If previous bit is 0 then next bit cannot be 1 if string[currlen - 1] == 0 and nextbit == 1: return # Otherwise else: string[currlen] = nextbit generateBinStr(string, length, currlen + 1, occur, 0) generateBinStr(string, length, currlen + 1, occur, 1) # Driver code if __name__ == "__main__": n = 5 # Length of the resulting strings # must be at least 4 if n < 4: print(-1) else: string = [None] * n # Generate all binary strings of length n # with sub-string "01" appearing twice generateBinStr(string, n, 0, 0, 0) generateBinStr(string, n, 0, 0, 1) # This code is contributed by Rituraj Jain
C#
// C# implementation of the above approach
using System;
class GFG
{
// Utility function to print the given binary string
static void printBinStr(int[] str, int len)
{
for (int i = 0; i < len; i++)
{
Console.Write(str[i]);
}
Console.Write("\n");
}
// This function will be called recursively
// to generate the next bit for given
// binary string according to its current state
static void generateBinStr(int[] str, int len, int currlen,
int occur, int nextbit)
{
// Base-case: if the generated binary string
// meets the required length and the pattern "01"
// appears twice
if (currlen == len)
{
// nextbit needs to be 0 because each time
// we call the function recursively,
// we call 2 times for 2 cases:
// next bit is 0 or 1
// The is to assure that the binary
// string is printed one time only
if (occur == 2 && nextbit == 0)
{
printBinStr(str, len);
}
return;
}
// Generate the next bit for str
// and call recursive
if (currlen == 0)
{
// Assign first bit
str[0] = nextbit;
// The next generated bit will wither be 0 or 1
generateBinStr(str, len, currlen + 1, occur, 0);
generateBinStr(str, len, currlen + 1, occur, 1);
} else // If pattern "01" occurrence is < 2
if (occur < 2)
{
// Set next bit
str[currlen] = nextbit;
// If pattern "01" appears then
// increase the occurrence of pattern
if (str[currlen - 1] == 0 && nextbit == 1)
{
occur += 1;
}
generateBinStr(str, len, currlen + 1, occur, 0);
generateBinStr(str, len, currlen + 1, occur, 1);
// Else pattern "01" occurrence equals 2
} else // If previous bit is 0 then next bit cannot be 1
if (str[currlen - 1] == 0 && nextbit == 1)
{
return;
// Otherwise
}
else
{
str[currlen] = nextbit;
generateBinStr(str, len, currlen + 1, occur, 0);
generateBinStr(str, len, currlen + 1, occur, 1);
}
}
// Driver code
public static void Main(String[] args)
{
int n = 5;
// Length of the resulting strings
// must be at least 4
if (n < 4)
{
Console.Write(-1);
}
else
{
int[] str = new int[n];
// Generate all binary strings of length n
// with sub-string "01" appearing twice
generateBinStr(str, n, 0, 0, 0);
generateBinStr(str, n, 0, 0, 1);
}
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript implementation of the approach
// Utility function to print the given binary string
function printBinStr(str, len)
{
for(var i = 0; i < len; i++)
{
document.write(str[i]);
}
document.write("<br>");
}
// This function will be called recursively
// to generate the next bit for given
// binary string according to its current state
function generateBinStr(str, len, currlen, occur, nextbit)
{
// Base-case: if the generated binary string
// meets the required length and the pattern "01"
// appears twice
if (currlen == len)
{
// nextbit needs to be 0 because each time
// we call the function recursively,
// we call 2 times for 2 cases:
// next bit is 0 or 1
// The is to assure that the binary
// string is printed one time only
if (occur == 2 && nextbit == 0)
printBinStr(str, len);
return;
}
// Generate the next bit for str
// and call recursive
if (currlen == 0)
{
// Assign first bit
str[0] = nextbit;
// The next generated bit will wither be 0 or 1
generateBinStr(str, len, currlen + 1, occur, 0);
generateBinStr(str, len, currlen + 1, occur, 1);
}
else
{
// If pattern "01" occurrence is < 2
if (occur < 2)
{
// Set next bit
str[currlen] = nextbit;
// If pattern "01" appears then
// increase the occurrence of pattern
if (str[currlen - 1] == 0 && nextbit == 1)
{
occur += 1;
}
generateBinStr(str, len,
currlen + 1, occur, 0);
generateBinStr(str, len,
currlen + 1, occur, 1);
}
// Else pattern "01" occurrence equals 2
else
{
// If previous bit is 0 then next
// bit cannot be 1
if (str[currlen - 1] == 0 && nextbit == 1)
{
return;
}
// Otherwise
else
{
str[currlen] = nextbit;
generateBinStr(str, len,
currlen + 1, occur, 0);
generateBinStr(str, len,
currlen + 1, occur, 1);
}
}
}
}
// Driver code
var n = 5;
// Length of the resulting strings
// must be at least 4
if (n < 4)
document.write(-1);
else
{
var str = Array(n);
// Generate all binary strings of length n
// with sub-string "01" appearing twice
generateBinStr(str, n, 0, 0, 0);
generateBinStr(str, n, 0, 0, 1);
}
// This code is contributed by importantly
</script>
Producción:
00101 01001 01010 01011 01101 10101
Publicación traducida automáticamente
Artículo escrito por GiaKhangLam y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA