# Find all binary strings that can be formed from given wildcard pattern

Given a binary pattern that contains ‘?’ wildcard character at few positions, find all possible combinations of binary strings that can be formed by replacing the wildcard character by either 0 or 1.

For example, for wildcard pattern 1?11?00?1?, the possible combinations are

1011000010
1011000011
1011000110
1011000111
1011100010
1011100011
1011100110
1011100111
1111000010
1111000011
1111000110
1111000111
1111100010
1111100011
1111100110
1111100111

##### Recursive solution –

We can easily solve this problem using recursion. The idea is to process each character of the pattern one by one and recurse for the remaining pattern. If the current digit is 0 or 1, we ignore it and if the current character is a wildcard character ‘?’, we replace it with 0 & 1 and recurse for the remaining pattern.

## Java

Output:

1011000010
1011000011
1011000110
1011000111
1011100010
1011100011
1011100110
1011100111
1111000010
1111000011
1111000110
1111000111
1111100010
1111100011
1111100110
1111100111

##### Iterative solution –

We can also solve this problem iteratively using stack, queue, set, vector or any other container. The idea remains the same. We start by processing each character of the pattern one by one but instead of recursing for the remaining pattern, we push it to a container. At each iteration, we pop a string from container, find first occurrence of wildcard pattern ‘?’ in it, replace ‘?’ with 0 & 1 and finally push it back to the container. If no wildcard pattern is found, print the popped string. We repeat this process until the container is empty.

## Java

Output:

1111100111
1111100110
1111100011
1111100010
1111000111
1111000110
1111000011
1111000010
1011100111
1011100110
1011100011
1011100010
1011000111
1011000110
1011000011
1011000010

The worst case time complexity of above solutions is exponential. Worst case happens when all the characters in the strings are ‘?’, there will be exponential strings possible in output. So this is the best time complexity we can achieve. For example, for str = “??????”, there are 64 strings in the output.

Best case time complexity of above solution is O(n). Best case occurs when string doesn’t contain any wildcard character ‘?’.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂

Get great deals at Amazon

Subscribe
Notify of
Guest
Top Coder

Good work.. never thought this problem can be solved iteratively using stack.

Guest
Abhishek

Why are we backtracking in the recursive code? The answer is the same even if we don’t backtrack(since we’re issuing a return statement)

Guest
Karan

Would it help in reducing the overhead if instead of just replacing each question mark with 0 and 1 every time, we look for find_last_of(‘?’) and also replace it with 0 and 1. I think the iterations would reduce for floor(current_iterations/2).

Here’s what I did for the if condition:
```if((index = curr.find_first_of('?')) != string::npos && (index2 = curr.find_last_of("?") != string::npos)) { for(size_t i = 0; i < 2; i++) { curr[index] = i + '0'; curr[index2] = i + '0'; list.push(curr); } }```