Generate all binary strings from pattern

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
11 upvotes
Asked in companies
AmazonMicrosoftCoinbase

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’.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
1?0
?
Sample Output 1:
110
100
0
1
Explanation of Sample Output 1:
In test case 1, There is only 1 ‘?’ at the second position, hence we can either replace it with either with 0 or 1, Hence 110 and 101 are the only two possible outputs.

In test case 2, There is only one special character which can be replaced by either 0 or 1, Hence 0 and 1 are the possible outputs.
Sample Input 2:
2
1??0
1??0?101
Sample Output 2:
1000
1010
1100
1110
10000101
10001101
10100101
10101101
11000101
11001101
11100101
11101101
Explanation of Sample Output 2:
In test case 1, '?' is present at 2,3 positions of the string, Hence there are 4 possible strings that can be formed by replacing '?' with 0 or 1 and they are 1000, 1010, 1100, 1110.

In test case 2, ‘?’ is present at 2,3 and 5 positions of the string. Hence there are 8 possible strings that can be formed by replacing '?' with 0 or 1 and they are 10000101, 10001101, 10100101, 10101101, 11000101, 11001101, 11100101, 11101101.

In test case 2,
Hint

Try to build all possible binary strings after replacing all ‘?’.

Approaches (2)
Recursive 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.
Time Complexity

O(2 ^ N), Where ‘N’ is the number of ‘?’ in the string.  

 

Since there are 2 possible combinations for every ‘?’ i.e replacing ‘?’ with 0 or 1. Hence for N special characters 2 ^ N operations will take place. Thus the time complexity will be O(2 ^ N).

Space Complexity

O(2 ^ N),  Where ‘N’ is the number of ‘?’ in the string. 

 

Since there are 2 possible combinations for every ‘?’ i.e replacing ‘?’ with 0 or 1. Hence for N special characters 2 ^ N strings will be formed and stored. Thus the space complexity will be O(2 ^ N).

Code Solution
(100% EXP penalty)
Generate all binary strings from pattern
Full screen
Console