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;
}
