题目描述
给你一个正整数 n
。
如果一个二进制字符串 x
的所有长度为 2
的子字符串中包含 至少 一个 “1”,则称 x
是一个 有效 字符串。
返回所有长度为 n
的 有效 字符串,可以以任意顺序排列。
样例
输入: n = 3
输出: ["010","011","101","110","111"]
解释:
长度为 3 的有效字符串有:"010"、"011"、"101"、"110" 和 "111"。
输入: n = 1
输出: ["0","1"]
解释:
长度为 1 的有效字符串有:"0" 和 "1"。
限制
1 <= n <= 18
算法
(暴力枚举) $O(n \cdot 2^n)$
- 暴力枚举所有的二进制数字,然后判断并记录答案。
时间复杂度
- 共有 $2^n$ 个数字,每个数字需要 $O(n)$ 的时间判断和存储答案,故时间复杂度为 $O(n \cdot 2^n)$。
空间复杂度
- 需要 $O(2^n)$ 的额外空间存储答案。
C++ 代码
class Solution {
public:
vector<string> validStrings(int n) {
vector<string> ans;
for (int s = 0; s < (1 << n); s++) {
string t;
bool ok = true;
int p = 1;
for (int i = 0; i < n; i++) {
int x = (s >> i) & 1;
if (x == 0 && p == 0) {
ok = false;
break;
}
p = x;
t += x + '0';
}
if (ok)
ans.emplace_back(t);
}
return ans;
}
};