Binary Strings | Google Interview Question

This problem has been presented many times in DS & Algo coding round. Please get familiar with how function recursion works. Recursion is the process of calling a function from within itself and I can't stress how many lines of code it can save when understood properly. This characteristic of recursion has made it a "no brainer" for the interviewer to choose a problem that would require recursion to solve.

PROBLEM

Given a string containing ‘0’, ‘1’ and ‘?’ wildcard characters, generate all binary strings that can be formed by replacing each wildcard character with ‘0’ or ‘1’.

Example 1 :   
Input str = "1??"

Output: 
        100
        110
        101
        111



Example 2 :


Input str = "1??0?101"

Output: 
        10000101
        10001101
        10100101
        10101101
        11000101
        11001101
        11100101
        11101101

        

Algorithm

Step 1: 

Convert the string to an array of characters.


Step 2: 

Loop through each character and if the character is a "?", then  replace it with "0" and recursively call the function for the next character.


Step 3: 

Now replace it with "1" and recursively call the fuction for the next character.


Step 4: 

If the character is not a "?" , then just proceed with the next character.


Step 5: 

When the last character is reached, log the result.

JavaScript Code

First, let's create a new prototype function for STRING as we will need this utility method to solve our problem.

String.prototype.replaceAt = function (index, replacement) {
  return this.substr(0, index) + replacement + this.substr(index + replacement.length);
}

Now let's write the actual function that prints binary strings.

function printBinaryStrings(str, i) {
  if (i === str.length) {
    console.log(str)
    return;
  }


  if (str[i] === '?') {

    str = str.replaceAt(i, '0');
    printBinaryStrings(str, i + 1)


    str = str.replaceAt(i, '1');
    printBinaryStrings(str, i + 1)


    str.replaceAt(i, '?');
  } else {
    printBinaryStrings(str, i + 1)
  }

}

printBinaryStrings('1??0?101', 0);

All the best,

Manoj