Skip to main content

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) 
    {
        BinaryText task = new BinaryText();

        // Test Inputs
        task.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
// 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()
{
	BinaryText *task = new BinaryText();
	// Test Inputs
	task->binaryString("11?11??10?");
	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)
	{
		BinaryText task = new BinaryText();
		// Test Inputs
		task.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
<?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()
{
	$task = new BinaryText();
	// Test Inputs
	$task->binaryString("11?11??10?");
}
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()
{
	var task = new BinaryText();
	// Test Inputs
	task.binaryString("11?11??10?");
}
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() :
	task = BinaryText()
	#  Test Inputs
	task.binaryString("11?11??10?")

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() 
	task = BinaryText.new()
	#  Test Inputs
	task.binaryString("11?11??10?")
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
		task.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
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()
{
	let task: BinaryText = BinaryText();
	// Test Inputs
	task.binaryString("11?11??10?");
}
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
{
	val task: BinaryText = BinaryText();
	// Test Inputs
	task.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
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).

Last updated on by Kalkicode




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.

New Comment