Generate all Binary Strings from Given Pattern

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; 
} 

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

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