Last Updated: 11 Jan, 2021

Generate all binary strings from pattern

Moderate

Asked in companies

Solve now

Problem statement

You're given a string 'STR' containing ‘0’, ‘1’ and ‘?’ special characters. Your task is to generate all the strings that are possible by replacing the special character ‘?’, with either of the characters ‘0’ or ‘1’.

Input Format:

The first line contains an integer 'T' denoting the number of test cases.

The first line and the only line of each test case contains a string 'STR' containing ‘1’, ‘0’, and ‘?’ only.

Output Format:

For each test case, return all the possible strings in a sorted order(from lexicographically smallest to largest) that can be generated in the manner as described in the problem statement.

Note:

1. You don’t need to print anything, It has already been taken care of. Just implement the given function.

2. It is guaranteed that the number of special characters will not be more than 14.

Constraints:

1 <= T <= 50
1 <= |STR| <= 30

Where '|STR|' denotes the length of the string 'STR'.

Time limit: 1 sec

Solve now

Approaches

01 Approach

In this approach we will be using recursion to reach all the possible binary strings.

We will start by making a function named binaryStrings(). Inside this, we will make an integer variable named index(initialised to be 0).

Now we check if the index is equal to the length of the string, if this condition is met we simply print that string.
Also, we check if the current character i.e ‘STR[index]’ is equal to ‘?’ or not. If it is equal to ‘?’, then we replace ‘?’ with both 0 and 1 and at the same time increment the index by 1.
We then recursively call the function again but this time the index is 1 more than the previous call.
If the current character i.e ‘STR[index]’ was not equal to ‘?’, then also we increment index by 1 and call the function again recursively.

For example: 1?0

We start traversing the indices of the string till we find ‘?’. On reaching the second index we encounter a ‘?’.
We then replace ‘?’ with 0(new string becomes 100) and recursively call the function again with index = 3 this time.
Similarly, we replace ‘?’ with 1(new string becomes 110) and recursively call the function again with index = 3 this time.
Now we see that our index is equal to the length of the string(100), hence we print 100.
Similarly, we see that our index is equal to the length of the string(110), hence we print 110.

Solve now

02 Approach

In this approach we will be reaching all the possible binary strings iteratively. Can you guess what data structure we’ll be using here? We will be using queue data structure to do this. We can also use stack, vector or any empty container to do this.

The steps are as follows:

We will find the position of the very first occurrence of ‘?’ in the given string.
We will replace this ‘?’ by ‘0’, then by ‘1’ and push both of these strings into the queue.
We then pop the next string from the queue.
We repeat this process till the queue is empty.
If no ‘?’ are left, we just print the string.

For example: 1?0

We start traversing the indices of the string till we find ‘?’. On reaching the second index we encounter a ‘?’.
We then replace ‘?’ by 0 and push 100 in the queue.
Similarly, we replace ‘?’ by 1 and push 110 in the queue.
Finally, when no ‘?’ are left, we simply print 100 and 110.

Solve now