generate_binary_strings.py

"""
# Generate Binary Strings Without Adjacent Zeros
You are given a positive integer n.
A binary string x is valid if all substrings of x of length 2 contain at least one "1".
Return all valid strings with length n, in any order.
"""

def valid_strings(n):
    solutions = []

    def backtrack(bits):
        if len(bits) == n: # accept
            solutions.append(''.join(bits))
            return

        for bit in ('0', '1'): # choices
            if bit == '0' and (bits and bits[-1] == '0'): # reject '00'
                continue
            bits.append(bit)
            backtrack(bits)
            bits.pop()

    backtrack([])
    return solutions


if __name__ == '__main__':
    from utils import test
    test(valid_strings(3), ["010","011","101","110","111"])
    test(valid_strings(1), ["0","1"])
    test(valid_strings(5), ['01010', '01011', '01101', '01110', '01111', '10101', '10110', '10111', '11010', '11011', '11101', '11110', '11111'])

    from utils import plot_time_complexity
    plot_time_complexity(valid_strings, lambda n: n, input_sizes=list(range(5, 21)))