Skip to content

3211. Generate Binary Strings Without Adjacent Zeros 👍

  • Time: $O(2^n)$
  • Space: $O(n \cdot 2^n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  vector<string> validStrings(int n) {
    vector<string> ans;
    dfs(n, "", ans);
    return ans;
  }

 private:
  void dfs(int n, string&& s, vector<string>& ans) {
    if (n == 0) {
      ans.push_back(s);
      return;
    }
    if (s.empty() || s.back() == '1') {
      s.push_back('0');
      dfs(n - 1, std::move(s), ans);
      s.pop_back();
    }
    s.push_back('1');
    dfs(n - 1, std::move(s), ans);
    s.pop_back();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public List<String> validStrings(int n) {
    List<String> ans = new ArrayList<>();
    dfs(n, new StringBuilder(), ans);
    return ans;
  }

  private void dfs(int n, StringBuilder s, List<String> ans) {
    if (n == 0) {
      ans.add(s.toString());
      return;
    }
    if (s.isEmpty() || s.charAt(s.length() - 1) == '1') {
      s.append('0');
      dfs(n - 1, s, ans);
      s.deleteCharAt(s.length() - 1);
    }
    s.append('1');
    dfs(n - 1, s, ans);
    s.deleteCharAt(s.length() - 1);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def validStrings(self, n: int) -> list[str]:
    ans = []

    def dfs(n: int, s: list[str]) -> None:
      if n == 0:
        ans.append(''.join(s))
        return
      if not s or s[-1] == '1':
        s.append('0')
        dfs(n - 1, s)
        s.pop()
      s.append('1')
      dfs(n - 1, s)
      s.pop()

    dfs(n, [])
    return ans