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