Posted on by Kalkicode
Code Backtracking

# Generate all binary strings from given pattern

The problem at hand is to generate all possible binary strings by replacing the question mark ('?') characters in a given pattern. The pattern contains binary digits ('0' or '1') along with question marks. We need to find all possible combinations of replacing the question marks with either '0' or '1'.

## Problem Statement and Description

Given a pattern string containing binary digits and question marks, we want to generate all possible binary strings by replacing the question marks with either '0' or '1'. For example, if the pattern is "11?11??10?", the valid binary strings could be "1101100100", "1101100101", "1101101100", and so on.

## Example

Let's take the pattern "11?11??10?" as an example. The question marks can be replaced with '0' or '1' to generate various binary strings:

Valid binary strings:

• "1101100100"
• "1101100101"
• "1101101100"
• "1101101101"
• ...
• "1111111101"

## Idea to Solve

To solve this problem, we can use a recursive approach. We'll start building the binary string from left to right, and at each position, if we encounter a question mark ('?'), we'll try both '0' and '1'. If the character is already a '0' or '1', we'll keep it as is.

## Pseudocode

Here's the pseudocode for the solution:

``````function generateBinaryStrings(text[], start, last):
if start == last:
print text
return

if text[start] is '?':
text[start] = '0'
generateBinaryStrings(text, start + 1, last)

text[start] = '1'
generateBinaryStrings(text, start + 1, last)

text[start] = '?'  // Reset to original value
else:
generateBinaryStrings(text, start + 1, last)

function generateAllBinaryStrings(text):
n = length of text
print "Given:", text
generateBinaryStrings(text, 0, n)

pattern = "11?11??10?"
generateAllBinaryStrings(pattern)``````

## Algorithm Explanation

1. Define a recursive function `generateBinaryStrings(text[], start, last)` that takes three parameters: the array `text` containing the pattern, the `start` position where we're currently processing, and `last` which is the length of the pattern.

2. If `start` reaches `last`, we have successfully generated a binary string by replacing all question marks, so we print it.

3. If the character at `text[start]` is a question mark ('?'), we replace it with '0' and recursively call `generateBinaryStrings` with `start + 1`.

4. Next, we replace the question mark with '1' and again recursively call `generateBinaryStrings` with `start + 1`.

5. After trying both '0' and '1', we reset the character at `text[start]` to a question mark since we want to explore other possibilities.

6. If the character is not a question mark, we don't need to replace it, so we just move forward by recursively calling `generateBinaryStrings` with `start + 1`.

7. Define the `generateAllBinaryStrings(text)` function which acts as a wrapper. Get the length `n` of the input pattern, then call `generateBinaryStrings(text, 0, n)` to generate all possible binary strings.

## Code Solution

``````/*
C program for
Generate all binary strings from given pattern
*/
#include <stdio.h>
#include <string.h>

void solution(char text[], int start, int last)
{
if (start == last)
{
printf(" %s \n", text);
return;
}
if (text[start] == '?')
{
// Change to 0
text[start] = '0';
solution(text, start + 1, last);
// Change to 1
text[start] = '1';
solution(text, start + 1, last);
// Assign original value
text[start] = '?';
}
else
{
solution(text, start + 1, last);
}
}
void binaryString(char text[])
{
int n = strlen(text);
// Display given pattern
printf("\n Given : %s \n", text);
// Find solution
solution(text, 0, n);
}
int main(int argc, char const *argv[])
{
char text[] = "11?11??10?";
// Test
binaryString(text);
return 0;
}``````

#### Output

`````` Given : 11?11??10?
1101100100
1101100101
1101101100
1101101101
1101110100
1101110101
1101111100
1101111101
1111100100
1111100101
1111101100
1111101101
1111110100
1111110101
1111111100
1111111101``````
``````/*
Java program for
Generate all binary strings from given pattern
*/

class BinaryText
{
public void generate(char[] text, int start, int last)
{
if (start == last)
{
System.out.println(text);
return;
}
if (text[start] == '?')
{
// Change to 0
text[start] = '0';
generate(text, start + 1, last);
// Change to 1
text[start] = '1';
generate(text, start + 1, last);
// Assign original value
text[start] = '?';
}
else
{
generate(text, start + 1, last);
}
}
public void binaryString(String text)
{
int n = text.length();

char []record = new char[n];

for (int i = 0; i < n ; ++i ) {

record[i] = text.charAt(i);
}
// Display given pattern
System.out.print("\nGiven : " + text + " \n");
// Find solution
this.generate(record, 0, n);
}
public static void main(String[] args)
{

// Test Inputs
}
}``````

#### Output

``````Given : 11?11??10?
1101100100
1101100101
1101101100
1101101101
1101110100
1101110101
1101111100
1101111101
1111100100
1111100101
1111101100
1111101101
1111110100
1111110101
1111111100
1111111101``````
``````// Include header file
#include <iostream>
#include <string>

using namespace std;
/*
C++ program for
Generate all binary strings from given pattern
*/
class BinaryText
{
public: void generate(char text[], int start, int last)
{
if (start == last)
{
cout << text << endl;
return;
}
if (text[start] == '?')
{
// Change to 0
text[start] = '0';
this->generate(text, start + 1, last);
// Change to 1
text[start] = '1';
this->generate(text, start + 1, last);
// Assign original value
text[start] = '?';
}
else
{
this->generate(text, start + 1, last);
}
}
void binaryString(string text)
{
int n = text.length();
char record[n+1];
for (int i = 0; i < n; ++i)
{
record[i] = text[i];
}
record[n] = '\0';
// Display given pattern
cout << "\nGiven : " << text << " \n";
// Find solution
this->generate(record, 0, n);
}
};
int main()
{
// Test Inputs
return 0;
}``````

#### Output

``````Given : 11?11??10?
1101100100
1101100101
1101101100
1101101101
1101110100
1101110101
1101111100
1101111101
1111100100
1111100101
1111101100
1111101101
1111110100
1111110101
1111111100
1111111101``````
``````// Include namespace system
using System;
/*
Csharp program for
Generate all binary strings from given pattern
*/
public class BinaryText
{
public void generate(char[] text, int start, int last)
{
if (start == last)
{
Console.WriteLine(text);
return;
}
if (text[start] == '?')
{
// Change to 0
text[start] = '0';
this.generate(text, start + 1, last);
// Change to 1
text[start] = '1';
this.generate(text, start + 1, last);
// Assign original value
text[start] = '?';
}
else
{
this.generate(text, start + 1, last);
}
}
public void binaryString(String text)
{
int n = text.Length;
// Use to collect result
char[] record = new char[n];
// Set initial value
for (int i = 0; i < n; ++i)
{
record[i] = text[i];
}
// Display given pattern
Console.Write("\nGiven : " + text + " \n");
// Find solution
this.generate(record, 0, n);
}
public static void Main(String[] args)
{
// Test Inputs
}
}``````

#### Output

``````Given : 11?11??10?
1101100100
1101100101
1101101100
1101101101
1101110100
1101110101
1101111100
1101111101
1111100100
1111100101
1111101100
1111101101
1111110100
1111110101
1111111100
1111111101``````
``````<?php
/*
Php program for
Generate all binary strings from given pattern
*/
class BinaryText
{
public	function generate(\$text, \$start, \$last)
{
if (\$start == \$last)
{
echo(implode("",\$text)."\n");
return;
}
if (\$text[\$start] == '?')
{
// Change to 0
\$text[\$start] = '0';
\$this->generate(\$text, \$start + 1, \$last);
// Change to 1
\$text[\$start] = '1';
\$this->generate(\$text, \$start + 1, \$last);
// Assign original value
\$text[\$start] = '?';
}
else
{
\$this->generate(\$text, \$start + 1, \$last);
}
}
public	function binaryString(\$text)
{
\$n = strlen(\$text);
// Use to collect result
\$record = array_fill(0, \$n, ' ');
// Set initial value
for (\$i = 0; \$i < \$n; ++\$i)
{
\$record[\$i] = \$text[\$i];
}
// Display given pattern
echo("\nGiven : ".\$text.
" \n");
// Find solution
\$this->generate(\$record, 0, \$n);
}
}

function main()
{
// Test Inputs
}
main();``````

#### Output

``````Given : 11?11??10?
1101100100
1101100101
1101101100
1101101101
1101110100
1101110101
1101111100
1101111101
1111100100
1111100101
1111101100
1111101101
1111110100
1111110101
1111111100
1111111101``````
``````/*
Node JS program for
Generate all binary strings from given pattern
*/
class BinaryText
{
generate(text, start, last)
{
if (start == last)
{
console.log(text.join(''));
return;
}
if (text[start] == '?')
{
// Change to 0
text[start] = '0';
this.generate(text, start + 1, last);
// Change to 1
text[start] = '1';
this.generate(text, start + 1, last);
// Assign original value
text[start] = '?';
}
else
{
this.generate(text, start + 1, last);
}
}
binaryString(text)
{
var n = text.length;
// Use to collect result
var record = Array(n).fill(' ');
// Set initial value
for (var i = 0; i < n; ++i)
{
record[i] = text.charAt(i);
}
// Display given pattern
process.stdout.write("\nGiven : " + text + " \n");
// Find solution
this.generate(record, 0, n);
}
}

function main()
{
// Test Inputs
}
main();``````

#### Output

``````Given : 11?11??10?
1101100100
1101100101
1101101100
1101101101
1101110100
1101110101
1101111100
1101111101
1111100100
1111100101
1111101100
1111101101
1111110100
1111110101
1111111100
1111111101``````
``````#    Python 3 program for
#    Generate all binary strings from given pattern
class BinaryText :
def generate(self, text, start, last) :
if (start == last) :
print("".join(text))
return

if (text[start] == '?') :
#  Change to 0
text[start] = '0'
self.generate(text, start + 1, last)
#  Change to 1
text[start] = '1'
self.generate(text, start + 1, last)
#  Assign original value
text[start] = '?'
else :
self.generate(text, start + 1, last)

def binaryString(self, text) :
n = len(text)
#  Use to collect result
record = [ ' '
] * (n)
i = 0
#  Set initial value
while (i < n) :
record[i] = text[i]
i += 1

#  Display given pattern
print("\nGiven : ", text ," ")
#  Find solution
self.generate(record, 0, n)

def main() :
#  Test Inputs

if __name__ == "__main__": main()``````

#### Output

``````Given :  11?11??10?
1101100100
1101100101
1101101100
1101101101
1101110100
1101110101
1101111100
1101111101
1111100100
1111100101
1111101100
1111101101
1111110100
1111110101
1111111100
1111111101``````
``````#    Ruby program for
#    Generate all binary strings from given pattern
class BinaryText
def generate(text, start, last)
if (start == last)
print(text.join(''), "\n")
return
end

if (text[start] == '?')
#  Change to 0
text[start] = '0'
self.generate(text, start + 1, last)
#  Change to 1
text[start] = '1'
self.generate(text, start + 1, last)
#  Assign original value
text[start] = '?'
else

self.generate(text, start + 1, last)
end

end

def binaryString(text)
n = text.length
#  Use to collect result
record = Array.new(n) { ' '
}
i = 0
#  Set initial value
while (i < n)
record[i] = text[i]
i += 1
end

#  Display given pattern
print("\nGiven : ", text ," \n")
#  Find solution
self.generate(record, 0, n)
end

end

def main()
#  Test Inputs
end

main()``````

#### Output

``````Given : 11?11??10?
1101100100
1101100101
1101101100
1101101101
1101110100
1101110101
1101111100
1101111101
1111100100
1111100101
1111101100
1111101101
1111110100
1111110101
1111111100
1111111101
``````
``````import scala.collection.mutable._;
/*
Scala program for
Generate all binary strings from given pattern
*/
class BinaryText()
{
def generate(text: Array[Char], start: Int, last: Int): Unit = {
if (start == last)
{
println(text.mkString(""));
return;
}
if (text(start) == '?')
{
// Change to 0
text(start) = '0';
generate(text, start + 1, last);
// Change to 1
text(start) = '1';
generate(text, start + 1, last);
// Assign original value
text(start) = '?';
}
else
{
generate(text, start + 1, last);
}
}
def binaryString(text: String): Unit = {
var n: Int = text.length();
// Use to collect result
var record: Array[Char] = Array.fill[Char](n)(' ');
var i: Int = 0;
// Set initial value
while (i < n)
{
record(i) = text.charAt(i);
i += 1;
}
// Display given pattern
print("\nGiven : " + text + " \n");
// Find solution
this.generate(record, 0, n);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: BinaryText = new BinaryText();
// Test Inputs
}
}``````

#### Output

``````Given : 11?11??10?
1101100100
1101100101
1101101100
1101101101
1101110100
1101110101
1101111100
1101111101
1111100100
1111100101
1111101100
1111101101
1111110100
1111110101
1111111100
1111111101``````
``````import Foundation;
/*
Swift 4 program for
Generate all binary strings from given pattern
*/
class BinaryText
{
func generate(_ text: inout[Character], _ start: Int, _ last: Int)
{
if (start == last)
{
print(String(text));
return;
}
if (text[start] == "?")
{
// Change to 0
text[start] = "0";
self.generate(&text, start + 1, last);
// Change to 1
text[start] = "1";
self.generate(&text, start + 1, last);
// Assign original value
text[start] = "?";
}
else
{
self.generate(&text, start + 1, last);
}
}
func binaryString(_ text: String)
{
let n: Int = text.count;
// Use to collect result
var record: [Character] = Array(text);
// Display given pattern
print("\nGiven : ", text ," ");
// Find solution
self.generate(&record, 0, n);
}
}
func main()
{
// Test Inputs
}
main();``````

#### Output

``````Given :  11?11??10?
1101100100
1101100101
1101101100
1101101101
1101110100
1101110101
1101111100
1101111101
1111100100
1111100101
1111101100
1111101101
1111110100
1111110101
1111111100
1111111101``````
``````/*
Kotlin program for
Generate all binary strings from given pattern
*/
class BinaryText
{
fun generate(text: Array < Char > , start: Int, last: Int): Unit
{
if (start == last)
{
println(text.joinToString(""));
return;
}
if (text[start] == '?')
{
// Change to 0
text[start] = '0';
this.generate(text, start + 1, last);
// Change to 1
text[start] = '1';
this.generate(text, start + 1, last);
// Assign original value
text[start] = '?';
}
else
{
this.generate(text, start + 1, last);
}
}
fun binaryString(text: String): Unit
{
val n: Int = text.length;
// Use to collect result
val record: Array < Char > = Array(n)
{
' '
};
var i: Int = 0;
// Set initial value
while (i < n)
{
record[i] = text.get(i);
i += 1;
}
// Display given pattern
print("\nGiven : " + text + " \n");
// Find solution
this.generate(record, 0, n);
}
}
fun main(args: Array < String > ): Unit
{
// Test Inputs
}``````

#### Output

``````Given : 11?11??10?
1101100100
1101100101
1101101100
1101101101
1101110100
1101110101
1101111100
1101111101
1111100100
1111100101
1111101100
1111101101
1111110100
1111110101
1111111100
1111111101``````
``````package main

import "fmt"
/*
Go program for
Generate all binary strings from given pattern
*/

func generate(text[] byte, start int, last int) {
if start == last {
fmt.Printf("%s\n",text)
return
}
if text[start] == '?' {
// Change to 0
text[start] = '0'
generate(text, start + 1, last)
// Change to 1
text[start] = '1'
generate(text, start + 1, last)
// Assign original value
text[start] = '?'
} else {
generate(text, start + 1, last)
}
}
func binaryString(text string) {
var n int = len(text)
// Use to collect result
var record = make([] byte,n)
// Set initial value
for i := 0 ; i < n ; i++ {
record[i] = text[i]
}
// Display given pattern
fmt.Print("\nGiven : ", text, " \n")
// Find solution
generate(record, 0, n)
}
func main() {

// Test Input
binaryString("11?11??10?")
}``````

#### Output

``````Given : 11?11??10?
1101100100
1101100101
1101101100
1101101101
1101110100
1101110101
1101111100
1101111101
1111100100
1111100101
1111101100
1111101101
1111110100
1111110101
1111111100
1111111101``````

## Time Complexity

The time complexity of this solution can be analyzed by considering the number of recursive calls. In the worst case, each position in the pattern can be a question mark ('?'), and for each position, we try both '0' and '1'. Therefore, the total number of recursive calls will be 2^k, where k is the number of question marks in the pattern. Thus, the time complexity is O(2^k).

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post