Description
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.
Example 1:
Input: n = 3
Output: ["010","011","101","110","111"]
Explanation:
The valid strings of length 3 are: "010", "011", "101", "110", and "111".
Example 2:
Input: n = 1
Output: ["0","1"]
Explanation:
The valid strings of length 1 are: "0" and "1".
Constraints:
1 <= n <= 18
Solution
Python3
class Solution:
def validStrings(self, n: int) -> List[str]:
res = []
def go(index, curr, prev):
if index == n:
nonlocal res
res.append(curr)
return
if prev is None:
go(index + 1, curr + "1", 1)
go(index + 1, curr + "0", 0)
else:
if prev == 0:
go(index + 1, curr + "1", 1)
else:
go(index + 1, curr + "1", 1)
go(index + 1, curr + "0", 0)
go(0, "", None)
return res