【每日题解】3211. 生成不含相邻零的二进制字符串

给你一个正整数 n。

如果一个二进制字符串 x 的所有长度为 2 的

子字符串

中包含 至少 一个 "1"，则称 x 是一个 有效 字符串。

返回所有长度为 n 的 有效 字符串，可以以任意顺序排列。

示例 1：

输入： n = 3

输出： ["010","011","101","110","111"]

解释：

长度为 3 的有效字符串有："010"、"011"、"101"、"110" 和 "111"。

示例 2：

输入： n = 1

输出： ["0","1"]

解释：

长度为 1 的有效字符串有："0" 和 "1"。

思路

• 如果我们有长度为 x 的字符串，根据二进制的规则，我们就能够生成长度为 x+1 的字符串（递归调用）
• 如果当前字符串以 0 结尾，我们只能向后补 1，否则出现 00，如果以 1 结尾，则可以补 0 或 1。

因此我们可以采用递归的思想，从长度为 1 的字符串开始生成，按照上面的逻辑生成全部长度为 n 的可能结果。

代码（C++）

class Solution {
public:vector<string> validStrings(int n) {vector<string> result;for (char start : {'0', '1'}) {backtrack(string(1, start), n, result);}return result;}void backtrack(string current, int n, vector<string>& result) {if (current.length() == n) {result.push_back(current);return;}if (current.back() == '0') {backtrack(current + '1', n, result);} else {backtrack(current + '0', n, result);backtrack(current + '1', n, result);}}
};

 代码（C++ 用队列逐层生成字符串）

class Solution {
public:vector<string> validStrings(int n) {vector<string> result;queue<string> q;q.push("0");q.push("1");while (!q.empty()) {string current = q.front();q.pop();if (current.length() == n) {result.push_back(current);continue;}if (current.back() == '0') {q.push(current + '1');} else {q.push(current + '1');q.push(current + '0');}}return result;}
};

代码（Python）

class Solution:def validStrings(self, n: int) -> List[str]:def backtrack(current):if len(current) == n:result.append(current)returnif current[-1] == '0':backtrack(current + '1')else:backtrack(current + '0')backtrack(current + '1')result = []for start in ['0', '1']:backtrack(start)return result