Generate all binary strings from pattern

Posted: 11 Jan, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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
Approach 1

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.
Try Problem