Find all binary strings that can be formed from wildcard pattern

Give a wildcard pattern “1?11?” of a binary string we have to find all the possible strings that can be formed by replacing ‘?’ with either ‘0’ or ‘1’.

Example

Input:
"1?11?"

Output:
"11111"
"11110"
"10111"
"10110"

This problem is classic example of backtracking technique and we will see both recursive as well as iterative solution for it.

Recursively find all binary strings from wildcard pattern using backtracking

In backtracking we explore all the possible options that can be made and then get or store only the desired result.

Conceptually this is how our solution works.

• Use an index and split the string into the character of array and using this track the wildcard pattern.
• Check if the character at current index is ‘?’ then replace it with ‘1’ and ‘0’ and recursively call the function for further pattern formation.
• At the end backtrack the current index back to ‘?’.

const printCombination = (pattern, i) => {
  
  //If desired length string is formed then print it
  if(i === pattern.length){
    console.log(pattern.join(""));
    return;
  }
  
  //If it is a wildcard pattern
  if(pattern[i] === '?'){
    
    for(let c = '0'; c <= '1'; c++){
      //Replace the wildcard with 0 and 1.
      pattern[i] = c;
      
      //Recursively call the samefunction for remaining pattern
      printCombination(pattern, i+1);
      
      //As array is passed as reference to the function, we can backtrack the pattern
      pattern[i] = '?';
    }
    
    return;
  }

Input:
printCombination("1?11?".split(""), 0);

Output:
"11111"
"11110"
"10111"
"10110"

Time complexity: The worst case time complexity for it is exponential and it occurs when the string contains only wild card patterns '?????', the best case time complexity is O(n) and it occurs when there is no wild card pattern in the string "10101".

Space complexity: Exponential.

---

Iterative solution to find the binary strings from wildcard pattern

The same problem can be solved iteratively using stack, queue, set or any other container. Here we are using stack.

• The idea remains the same we store the string in the stack and start iteration till stack is not empty.
• In each iteration get the top string from the stack and find its first wildcard pattern and replace it with either '0' or '1' and push it back to the container.
• If there is no wildcard then print the string.

const printCombinationIterative = (pattern) => {
  //Create a stack
  const stack = [];
  
  //Push the pattern in the stack
  stack.push(pattern);
  
  //To track the index of wildcard
  let index;
  
  while(stack.length){
    //Get the pattern
    let curr = stack.pop();
    
    //Find the index of the wildcard pattern and store in the index 
    //and simultaneously check if it is present or not
    if((index = curr.indexOf('?')) !== -1){
        //Replace the '?' with '0' and '1' and store it back in the stack
        for(let c = '0'; c <= '1'; c++){
          curr = curr.substring(0, index) + c + curr.substring(index+1);
          stack.push(curr);
        }
    }else{
      //If there is no wildcard present then print the string
      console.log(curr);
    }
  }
}

Input:
printCombinationIterative("1?11?");

Output:
"11111"
"11110"
"10111"
"10110"

Time and Space complexity is same as the recursive solution.