Generate Binary Strings Without Consecutive Ones
Easy
Given an integer n, generate all binary strings of length n such that no two adjacent characters are both '1'. Return the result as a stringified JSON array of strings sorted in lexicographical order.
Example 1
Input
[ "1" ]
Output
[ "0", "1" ]
Explanation. For n = 1, both '0' and '1' do not contain consecutive ones.
Example 2
Input
[ "2" ]
Output
[ "00", "01", "10" ]
Explanation. For n = 2, '00', '01', and '10' are valid. '11' is omitted because it has two consecutive ones.
Example 3
Input
[ "3" ]
Output
[ "000", "001", "010", "100", "101" ]
Explanation. For n = 3, there are 5 valid binary strings in lexicographical order.
Example 4
Input
[ "4" ]
Output
[ "0000", "0001", "0010", "0100", "0101", "1000", "1001", "1010" ]
Explanation. For n = 4, there are 8 valid binary strings in lexicographical order.
Follow-up: How would you find the total count of such valid binary strings for a larger n using dynamic programming instead of generating them with backtracking?
Constraints:
1 <= n <= 15
- Views
- 2