Home » Interview Questions » String Interview Questions » Generate all binary strings from given pattern

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

 

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions