Comment on page
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
Last modified 4yr ago