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 recuse 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 recuse for the remaining pattern.

 
C++ implementation –
 

Download   Run Code

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 recusing 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.

 
C++ implementation –
 

Download   Run Code

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 ‘?’.

 
Thanks for reading.




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 🙂
 


    

  • Top Coder

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