Generate all binary strings from given pattern

0
296
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

 

LEAVE A REPLY

Please enter your comment!
Please enter your name here