Binary Replacement

Write a program that takes in a binary string that also contains x's and prints out all possible binary strings where each x can be replaced with either a 0 or 1.

Example

input: 1010
output: [1010]

input: xx
output: [00, 01, 10, 11]

input: 1x0X
output: [1000, 1001, 1100, 1101]

The Idea: Iterate through the string: when there is an x, append both 0 and 1 to the string, and branch out on each one of these cases. Otherwise just branch by 1.

Complexity: O(2^n + |S| - n) where n is the number of 'x's, and S is the length of the string.

import queue


def binary_replacement(str):
    if not str:
        return []

    q = queue.Queue()
    q.put(('', -1))
    sol = []

    while not q.empty():
        cum_str, i = q.get()

        if i + 1 >= len(str):
            sol.append(cum_str)
            while not q.empty():
                sol.append(q.get()[0])
            return sol

        cur_char = str[i+1]
        if cur_char == 'x' or cur_char == 'X':
            q.put((cum_str + '0', i + 1))
            q.put((cum_str + '1', i + 1))
        else:
            q.put((cum_str + cur_char, i + 1))


print(binary_replacement('xx'))
print(binary_replacement('1x0X'))
print(binary_replacement('1010'))

Recursive Approach

def binary_replacement(bx):
    sol = []
    def dfs(i, cur):
        if len(cur) == len(bx):
            sol.append(cur)
            return
        else:
            if bx[i].lower() != 'x':
                dfs(i+1, cur+bx[i])
            else:
                dfs(i+1, cur+'1')
                dfs(i+1, cur+'0')
    dfs(0, '')
    return sol