Generate all binary strings from given pattern

The given input string consists of 0, 1 and ? (wildcard char), we need to generate all possible binary strings by replacing ? with ‘0’ and ‘1’.

Examples

a) Input string : “1?1”
    Output : 101, 111

b) Input string : 1?0?1?1
    Output : 1000101
        1000111
        1001101
        1001111
        1100101
        1100111
        1101101
        1101111

Time complexity : O(logn)

Algorithm

We use recursion,

1. If current character is ?,. we replace it by ‘0’ or ‘1’.

2. If we find ? we replace with ‘0’ and continue recursion.

3. Then, replace ? with ‘1’ and continue recursion

4. We recurse for remaining characters.

5. We print the string if we reaches its end.

C++ Program

#include <bits/stdc++.h>

using namespace std;

void PrintStrings(string str, int index)
{
    if(index == str.size())//Print if it reaches the end.
    {
        cout << str << endl;
        return;
    }
 
    if(str[index] == '?')//If ?
    {
        str[index] = '0';//Replace with '0' and continue recursion
        PrintStrings(str, index + 1);
        str[index] = '1';//Replace with '1' and continue recursion
        PrintStrings(str, index + 1);
    }
    else//If 0 or 1  move forward
    {
        PrintStrings(str, index + 1);
    }
}
 
//Main function
int main()
{
    string Input_string = "1?0?1?1";
    PrintStrings(Input_string, 0);
    return 0;
}
Try It

 


Next > < Prev
Scroll to Top