Generate all binary strings from given pattern - GeeksforGeeks
Given a string containing of '0', '1' and '?' wildcard characters, generate all binary strings that can be formed by replacing each wildcard character by '0' or '1'.
Read full article from Generate all binary strings from given pattern - GeeksforGeeks
Given a string containing of '0', '1' and '?' wildcard characters, generate all binary strings that can be formed by replacing each wildcard character by '0' or '1'.
Input str = "1??0?101"
Output:
10000101
10001101
10100101
10101101
11000101
11001101
11100101
11101101
We pass index of next character to the recursive function. If the current character is a wildcard character ‘?’, we replace it by ‘0’ or ‘1’ and recurse for remaining characters. We print the string if we reaches its end.void print(string str, int index){ if (index == str.size()) { cout << str << endl; return; } if (str[index] == '?') { // replace '?' by '0' and recurse str[index] = '0'; print(str, index + 1); // replace '?' by '1' and recurse str[index] = '1'; print(str, index + 1); // No need to backtrack as string is passed // by value to the function } else print(str, index + 1);}// Iterative function to generate all binary strings// formed by replacing each wildcard character by 0// or 1void print(string str){ queue<string> q; q.push(str); while (!q.empty()) { string str = q.front(); // find position of first occurrence of wildcard size_t index = str.find('?'); // If no matches were found, // find returns string::npos if(index != string::npos) { // replace '?' by '0' and push string into queue str[index] = '0'; q.push(str); // replace '?' by '1' and push string into queue str[index] = '1'; q.push(str); } else // If no wildcard characters are left, // print the string. cout << str << endl; q.pop(); }}