LeetCode 题解工作台
生成不含相邻零的二进制字符串
给你一个正整数 n 。 如果一个二进制字符串 x 的所有长度为 2 的 子字符串 中包含 至少 一个 "1" ，则称 x 是一个 有效 字符串。 返回所有长度为 n 的 有效 字符串，可以以任意顺序排列。 示例 1： 输入： n = 3 输出： ["010","011","101","110","1…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 回溯·pruning
答案摘要
我们可以枚举长度为 的二进制字符串的每个位置 ，然后对于每个位置 ，我们可以枚举其可以取的值 ，如果 为 ，那么我们需要判断其前一个位置是否为 ，如果为 ，则可以继续递归下去，否则不合法，如果 为 ，则直接递归下去。 时间复杂度 $O(n \times 2^n)$，其中 为字符串长度。忽略答案数组的空间消耗，空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 回溯·pruning 题型思路
题目描述
给你一个正整数 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"。
提示：
1 <= n <= 18
解题思路
方法一：DFS
我们可以枚举长度为 的二进制字符串的每个位置 ，然后对于每个位置 ，我们可以枚举其可以取的值 ，如果 为 ，那么我们需要判断其前一个位置是否为 ，如果为 ，则可以继续递归下去，否则不合法，如果 为 ，则直接递归下去。
时间复杂度 ，其中 为字符串长度。忽略答案数组的空间消耗，空间复杂度 。
class Solution:
def validStrings(self, n: int) -> List[str]:
def dfs(i: int):
if i >= n:
ans.append("".join(t))
return
for j in range(2):
if (j == 0 and (i == 0 or t[i - 1] == "1")) or j == 1:
t.append(str(j))
dfs(i + 1)
t.pop()
ans = []
t = []
dfs(0)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect an understanding of recursive generation and pruning strategies for string enumeration.
- question_mark
Check if you consider the constraint preventing consecutive zeros before recursion.
- question_mark
Notice if the candidate optimizes memory or speed using bit-level representation.
常见陷阱
外企场景- error
Appending 0 without checking the previous character leads to invalid strings.
- error
Trying to generate all 2^n strings before filtering is inefficient and fails for larger n.
- error
Forgetting to collect strings only after reaching length n can create duplicates or incomplete results.
进阶变体
外企场景- arrow_right_alt
Generate ternary strings avoiding two consecutive zeros or twos.
- arrow_right_alt
Count the number of valid strings instead of listing them, which reduces memory use.
- arrow_right_alt
Modify the pattern to avoid k consecutive zeros instead of just two.