aboutsummaryrefslogtreecommitdiff
path: root/generate_binary_string_without_adj_0.py
blob: 566915624031ec868ac79d15a5bf041d3d8c0654 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# 3211. 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.
"""


class Solution(object):
    def __init__(self):
        self.ans = []

    def dfs(self, prev, str, n):
        if len(str) == n:
            self.ans.append(str)
            return
        self.dfs(1, str + "1", n)
        if prev == 1:
            self.dfs(0, str + "0", n)

    def validStrings(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        self.ans = []
        self.dfs(0, "0", n)
        self.dfs(1, "1", n)
        return self.ans


if __name__ == "__main__":
    obj = Solution()
    print(obj.validStrings(n=3))
    print(obj.validStrings(n=1))