Teaching Kids Programming – Generate Binary Strings Without Adjacent Zeros (Breadth First Search Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

Generate Binary Strings Without Adjacent Zeros (Breadth First Search Algorithm)

Last time, we talked about using the Depth First Search Algorithm (Recursive Version) to traversal the tree when we expand the next binary character. We can of course use the BFS (Breadth First Search).

In this problem, both tree (binary tree) traversal algorithms have the same time/space complexity, as the requirements for valid binary strings are the same: Size N and without Adjacent Zeros.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def validStrings(self, n: int) -> List[str]:
        q = deque([[]])
        ans = []
        while q:
            cur = q.popleft()
            if len(cur) == n:
                ans.append("".join(cur))
            else:
                if len(cur) == 0 or cur[-1] == '1':
                    q.append(cur + ['0'])
                q.append(cur + ['1'])
        return ans

class Solution:
    def validStrings(self, n: int) -> List[str]:
        q = deque([[]])
        ans = []
        while q:
            cur = q.popleft()
            if len(cur) == n:
                ans.append("".join(cur))
            else:
                if len(cur) == 0 or cur[-1] == '1':
                    q.append(cur + ['0'])
                q.append(cur + ['1'])
        return ans

If we change the queue to stack, we are actually performing a Depth First Search Algorithm but in the iterative manner. For BFS, we can expand the children nodes at one level all at once, alternatively, we can enqueue a child node one by one.

Generate Binary Strings Without Adjacent Zeros

• Teaching Kids Programming - Another BFS to Generate Binary Strings Without Adjacent Zeros
• Teaching Kids Programming - Generate Binary Strings Without Adjacent Zeros (Breadth First Search Algorithm)
• Teaching Kids Programming - Generate Binary Strings Without Adjacent Zeros (Recursive Depth First Search Algorithm)

–EOF (The Ultimate Computing & Technology Blog) —