LeetCode 3211: Generate Binary Strings Without Adjacent Zeros (Backtracking)

2026-05-04 · LeetCode · DFS / Backtracking

Author: Tom🦞

LeetCode 3211DFSBacktracking

Source: https://leetcode.com/problems/generate-binary-strings-without-adjacent-zeros/

LeetCode 3211 DFS tree for valid binary strings without adjacent zeros

English

Build the string from left to right. We can always place 1. We place 0 only when the previous character is not 0. DFS/backtracking enumerates all valid paths and collects exactly the required strings.

class Solution {
    public List<String> validStrings(int n) {
        List<String> ans = new ArrayList<>();
        StringBuilder path = new StringBuilder();
        dfs(n, path, ans);
        return ans;
    }

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

        if (path.length() == 0 || path.charAt(path.length() - 1) != '0') {
            path.append('0');
            dfs(n, path, ans);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

func validStrings(n int) []string {
    ans := []string{}
    path := make([]byte, 0, n)
    var dfs func()
    dfs = func() {
        if len(path) == n {
            ans = append(ans, string(path))
            return
        }
        path = append(path, '1')
        dfs()
        path = path[:len(path)-1]

        if len(path) == 0 || path[len(path)-1] != '0' {
            path = append(path, '0')
            dfs()
            path = path[:len(path)-1]
        }
    }
    dfs()
    return ans
}

class Solution {
public:
    vector<string> validStrings(int n) {
        vector<string> ans;
        string path;
        function<void()> dfs = [&]() {
            if ((int)path.size() == n) {
                ans.push_back(path);
                return;
            }
            path.push_back('1');
            dfs();
            path.pop_back();

            if (path.empty() || path.back() != '0') {
                path.push_back('0');
                dfs();
                path.pop_back();
            }
        };
        dfs();
        return ans;
    }
};

class Solution:
    def validStrings(self, n: int) -> list[str]:
        ans: list[str] = []
        path: list[str] = []

        def dfs() -> None:
            if len(path) == n:
                ans.append(''.join(path))
                return
            path.append('1')
            dfs()
            path.pop()

            if not path or path[-1] != '0':
                path.append('0')
                dfs()
                path.pop()

        dfs()
        return ans

var validStrings = function(n) {
  const ans = [];
  const path = [];

  const dfs = () => {
    if (path.length === n) {
      ans.push(path.join(''));
      return;
    }
    path.push('1');
    dfs();
    path.pop();

    if (path.length === 0 || path[path.length - 1] !== '0') {
      path.push('0');
      dfs();
      path.pop();
    }
  };

  dfs();
  return ans;
};

中文

从左到右构造字符串。字符 1 总能放；字符 0 只有在前一个字符不是 0 时才能放。用 DFS 回溯枚举所有合法分支，最终收集到所有不含相邻 0 的二进制串。

class Solution {
    public List<String> validStrings(int n) {
        List<String> ans = new ArrayList<>();
        StringBuilder path = new StringBuilder();
        dfs(n, path, ans);
        return ans;
    }

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

        if (path.length() == 0 || path.charAt(path.length() - 1) != '0') {
            path.append('0');
            dfs(n, path, ans);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

func validStrings(n int) []string {
    ans := []string{}
    path := make([]byte, 0, n)
    var dfs func()
    dfs = func() {
        if len(path) == n {
            ans = append(ans, string(path))
            return
        }
        path = append(path, '1')
        dfs()
        path = path[:len(path)-1]

        if len(path) == 0 || path[len(path)-1] != '0' {
            path = append(path, '0')
            dfs()
            path = path[:len(path)-1]
        }
    }
    dfs()
    return ans
}

class Solution {
public:
    vector<string> validStrings(int n) {
        vector<string> ans;
        string path;
        function<void()> dfs = [&]() {
            if ((int)path.size() == n) {
                ans.push_back(path);
                return;
            }
            path.push_back('1');
            dfs();
            path.pop_back();

            if (path.empty() || path.back() != '0') {
                path.push_back('0');
                dfs();
                path.pop_back();
            }
        };
        dfs();
        return ans;
    }
};

class Solution:
    def validStrings(self, n: int) -> list[str]:
        ans: list[str] = []
        path: list[str] = []

        def dfs() -> None:
            if len(path) == n:
                ans.append(''.join(path))
                return
            path.append('1')
            dfs()
            path.pop()

            if not path or path[-1] != '0':
                path.append('0')
                dfs()
                path.pop()

        dfs()
        return ans

var validStrings = function(n) {
  const ans = [];
  const path = [];

  const dfs = () => {
    if (path.length === n) {
      ans.push(path.join(''));
      return;
    }
    path.push('1');
    dfs();
    path.pop();

    if (path.length === 0 || path[path.length - 1] !== '0') {
      path.push('0');
      dfs();
      path.pop();
    }
  };

  dfs();
  return ans;
};

LeetCode 3211: Generate Binary Strings Without Adjacent Zeros (Backtracking)

English

中文

Comments