Table of Contents

## Problem Statement

In the “Generate all Binary Strings from Given Pattern” problem we have given input string “s” consists of 0, 1, and ? (wildcard char). We need to generate all possible binary strings by replacing ? with ‘0’ and ‘1’.

## Input Format

The first and only one line containing a string “s”.

## Output Format

Print 2^n lines where every line containing a string represent a binary string. Here n is the number of “?” char in the given string “s”.

## Constraints

- 1<=|s|<=15
- s[i] must be a digit(0-9) or “?”

## Example

1?1

101 111

**Explanation:** The value of n(no. of ‘?’ in the string) is 1 at here. So, there are two string possible 101 and 111.

1?0?1?1

1000101 1000111 1001101 1001111 1100101 1100111 1101101 1101111

**Explanation:** The value of n(no. of ‘?’ in the string) is 3 at here. So, there are 8 string possible 1000101, 1000111, 1001101, 1001111, 1100101, 1100111, 1101101, 1101111.

## Algorithm to Generate all Binary Strings from Given Pattern

We can achieve this by using iteration. The idea is to use queue. We find position of first occurrence of wildcard character in the input string and replace it by ‘0’ , then ‘1’ and push both strings into the queue. Then we pop next string from the queue, and repeat the process till queue is empty. If no wildcard characters are left, we simply print the string.

- Take input given string “s”.
- Push given string into the queue.
- Repeat till queue is not empty:

1. Now, store the queue front value into a string.

2. Find the position of the first occurrence of “?”.

3. If no matches were found, find returns string::npos.

3.1 replace ‘?’ by ‘0’ and push string into queue.

3.2 replace ‘?’ by ‘1’ and push string into queue.

4. If no wildcard characters are left, print the string.

5. Pop the string from queue.

## Implementation

### C++ Program to Generate all Binary Strings from Given Pattern

#include <bits/stdc++.h> using namespace std; int main() { string s; cin>>s; queue<string> q; q.push(s); while (!q.empty()) { string temp = q.front(); size_t index = temp.find('?'); if(index != string::npos) { temp[index] = '0'; q.push(temp); temp[index] = '1'; q.push(temp); } else { cout<<temp<<endl; } q.pop(); } return 0; }

### Java Program to Generate all Binary Strings from Given Pattern

import java.util.Scanner; import java.util.Stack; class sum { public static void main(String[] args) { Scanner sr = new Scanner(System.in); String s = sr.next(); Stack<String> stack = new Stack(); stack.push(s); int index; while(!stack.empty()) { String curr = stack.pop(); if((index = curr.indexOf('?')) != -1) { for (char ch = '0'; ch <= '1'; ch++) { curr = curr.substring(0, index) + ch + curr.substring(index + 1); stack.push(curr); } } else System.out.println(curr); } } }

1?01?

11011 11010 10011 10010

## Complexity Analysis to Generate all Binary Strings from Given Pattern

### Time Complexity

**O(2^n)** where **n** is the number of wildcard numbers on the string.

### Space Complexity

**O(m*(2^n))** where **m** is the size of the string “s” and **n** is the number of wildcard in the string.