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