_3211. Generate Binary Strings Without Adjacent Zeros.md

3211. Generate Binary Strings Without Adjacent Zeros

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Completed during Weekly Contest 405 (q2)

Back to top

---

First completed : July 07, 2024

Last updated : July 09, 2024

---

Related Topics : String, Bit Manipulation, Recursion

Acceptance Rate : 86.6 %

---

Solutions

• m3211.js
• Weekly Contest 405/m3211 q2.py

JavaScript

m3211.js

/**
 * @param {number} n
 * @return {string[]}
 */
var validStrings = function(n) {
    const outputs = [];

    function propogate(curr, r) {
        if (r === 0) {
            outputs.push(curr.join(''));
            return;
        }

        if (r == 1) {
            outputs.push(curr.join('') + '0');
            outputs.push(curr.join('') + '1');
            return;
        }

        curr.push('1');
        propogate(curr, r - 1);
        curr.pop();
        curr.push('01');
        propogate(curr, r - 2);
        curr.pop();
    }

    propogate([], n);
    return outputs;
};

Python

m3211 q2.py

class Solution:
    def validStrings(self, n: int) -> List[str]:
        output = []

        def dfs(curr: List[str], 
                output: List[str], 
                remaining: int, 
                prevIsOne: bool) -> None :
            if not remaining :
                output.append(''.join(curr))
                return
            
            curr.append('1')
            remaining -= 1
            dfs(curr, output, remaining, True)
            curr.pop()

            if prevIsOne :
                curr.append('0')
                dfs(curr, output, remaining, False)
                curr.pop()
        dfs([], output, n, True)
        return output