LeetCode 3211中等回溯 · 枚举
生成不含相邻零的二进制字符串 图解题解
这道题到底在问什么
给定正整数 n(1 ≤ n ≤ 18)。若一个二进制串的每一个长度为 2 的子串里都至少有一个 1,就称它有效。返回所有长度为 n 的有效串,顺序任意。每个长度为 2 的子串都含 1,等价于说串里不出现连续两个 0。
- 输入
- n = 3
- 输出
- ["010","011","101","110","111"] 共 5 个
- 输入
- n = 1
- 输出
- ["0","1"] 共 2 个
最优解：一步一步想明白
- 3记牢这套口诀:填 1 随便填,填 0 先看上一位,填满就收,走到头就回退换下一种。下面每一帧都在套它,舞台上方是这一位的两个候选,中间是正在拼的串 path,下面是已经收下的合法串。
- 4先看舞台。上面「可选数字」是每一位的两个候选,填 0 或者填 1;中间 path 是正在拼的串,现在还是空的;下面 res 收集所有拼满且合法的串。我们从第 1 位开始,先试着填 0。
- 5第 1 位填 0,这是第一位,前面没有别的位,填 0 安全。现在 path 是 0,往下钻去定第 2 位。
- 6走到第 2 位,想填 0,先看上一位。上一位是 0,要是这位再填 0,就凑出了连续两个 0,违反规则。所以把候选里的 0 划掉,这一位不能填 0,只能改填 1。
- 7第 2 位填 1,现在 path 是 01。填 1 永远安全,不用检查。往下钻,去定第 3 位。
- 8第 3 位填 0,上一位是 1,不会出现 00,凑齐了长度 3。这一串 010 合法,收进结果,现在已经收了 1 个。
- 9这条路拼满了,把末位的 0 收回来,path 退回 01,回到上一位换下一种填法。这就是回溯:退一步,才好探另一条路。
- 10第 3 位填 1,凑齐了长度 3。1 不会和前面凑成 00,这一串 011 合法,收进结果,现在已经收了 2 个。
- 11这条路拼满了,把末位的 1 收回来,path 退回 01,回到上一位换下一种填法。这就是回溯:退一步,才好探另一条路。
- 12这条路能试的都试过了,把末位的 1 收回来,path 退回 0,回到上一位换下一种填法。这就是回溯:退一步,才好探另一条路。
- 13这条路能试的都试过了,把末位的 0 收回来,path 退回 空,回到上一位换下一种填法。这就是回溯:退一步,才好探另一条路。
- 14第 1 位填 1,现在 path 是 1。填 1 永远安全,不用检查。往下钻,去定第 2 位。
- 15第 2 位填 0,上一位是 1,填 0 不会出现 00。现在 path 是 10,往下钻去定第 3 位。
- 16走到第 3 位,想填 0,先看上一位。上一位是 0,要是这位再填 0,就凑出了连续两个 0,违反规则。所以把候选里的 0 划掉,这一位不能填 0,只能改填 1。
- 17第 3 位填 1,凑齐了长度 3。1 不会和前面凑成 00,这一串 101 合法,收进结果,现在已经收了 3 个。
- 18这条路拼满了,把末位的 1 收回来,path 退回 10,回到上一位换下一种填法。这就是回溯:退一步,才好探另一条路。
- 19这条路能试的都试过了,把末位的 0 收回来,path 退回 1,回到上一位换下一种填法。这就是回溯:退一步,才好探另一条路。
- 20第 2 位填 1,现在 path 是 11。填 1 永远安全,不用检查。往下钻,去定第 3 位。
- 21第 3 位填 0,上一位是 1,不会出现 00,凑齐了长度 3。这一串 110 合法,收进结果,现在已经收了 4 个。
- 22这条路拼满了,把末位的 0 收回来,path 退回 11,回到上一位换下一种填法。这就是回溯:退一步,才好探另一条路。
- 23第 3 位填 1,凑齐了长度 3。1 不会和前面凑成 00,这一串 111 合法,收进结果,现在已经收了 5 个。
- 24这条路拼满了,把末位的 1 收回来,path 退回 11,回到上一位换下一种填法。这就是回溯:退一步,才好探另一条路。
- 25这条路能试的都试过了,把末位的 1 收回来,path 退回 1,回到上一位换下一种填法。这就是回溯:退一步,才好探另一条路。
- 26这条路能试的都试过了,把末位的 1 收回来,path 退回 空,回到上一位换下一种填法。这就是回溯:退一步,才好探另一条路。
- 27所有分支都搜遍了,右边正好收了 5 个合法串:010、011、101、110、111。它们的共同点是任意相邻两位都不同时为 0。这就是 n 等于 3 的答案,一个不多一个不少。
⚠️ 容易写错的地方
✗ 错：把条件记成不能出现连续两个 1
✓ 对：是不能出现连续两个 0
题目要每段相邻两位都含 1,反面是不许挨着两个 0;记反了会把 011、111 这些合法串误删
✗ 错：填 0 时不看上一位就直接填
✓ 对：填 0 前先确认在开头或上一位是 1
不检查就会在上一位是 0 时又填 0,拼出含 00 的非法串
✗ 错：填 1 时也去做同样的合法性检查
✓ 对：填 1 无条件允许,不必检查
1 不可能和任何位凑成 00,多做判断没意义还容易写错分支
✗ 错：递归返回后忘了把这一位撤掉
✓ 对：回来立刻 pop 掉末位再换下一种
不撤销,path 会越拼越长、脏数据串进兄弟分支,漏掉一大批答案
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
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 ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
vector<string> validStrings(int n) {
vector<string> ans;
string t;
function<void(int)> dfs = [&]( int i ) {
if (i >= n) {
ans.emplace_back(t);
return;
}
for (int j = 0; j < 2; ++j) {
if ((j == 0 && (i == 0 || t[i - 1] == '1')) || j == 1) {
t.push_back('0' + j);
dfs(i + 1);
t.pop_back();
}
}
};
dfs(0);
return ans;
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
private List<String> ans = new ArrayList<>();
private StringBuilder t = new StringBuilder();
private int n;
public List<String> validStrings(int n) {
this.n = n;
dfs(0);
return ans;
}
private void dfs(int i) {
if (i >= n) {
ans.add(t.toString());
return;
}
for (int j = 0; j < 2; ++j) {
if ((j == 0 && (i == 0 || t.charAt(i - 1) == '1')) || j == 1) {
t.append(j);
dfs(i + 1);
t.deleteCharAt(t.length() - 1);
}
}
}
}复杂度
时间
O(n · 2^n)
上界是长度 n 的二进制串一共 2 的 n 次方个,回溯会把不合法的分支提前剪掉,实际有效串数是斐波那契级别、约 φ 的 n 次方(φ 约 1.618),每收一个串复制一次要 O(n)。所以时间随 n 指数增长,题目把 n 限制在 18 以内正是因为结果本身就是指数量级
空间
O(n)
按峰值算,不计输出本身。递归最深就是 n 层,path 最长也是 n 个字符,两者都是 O(n)。收集到的所有结果串是必须返回的输出,一般不计入额外空间
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 生成不含相邻零的二进制字符串 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题的核心思路是什么?+
把长度 n 的二进制串一位一位地构造,用回溯枚举所有合法填法。每一位试填 0 和 1:填 1 无条件允许,填 0 只有在开头或上一位是 1 时才允许,这个约束保证不出现连续两个 0。填满 n 位就把这一串收进答案,走到头就撤掉末位换下一种,直到搜遍。
除了回溯,还有别的做法吗?+
可以用动态规划按合法串数量递推,合法串的数量满足斐波那契关系,但本题要的是把所有串都列出来,不只是计数,所以最终仍要枚举。也可以用递推按上一位是 0 还是 1 分两组增量地拼,本质和回溯等价。回溯写起来最直观,直接对着约束试填即可。
为什么时间是指数级,n 却只到 18?+
因为答案本身就是指数级的:合法串数量约是 φ 的 n 次方,φ 约 1.618,n 等于 18 时也就几千个,列全部串必然要指数时间和输出规模。把 n 限制在 18 以内,正是为了让结果集不至于爆炸,回溯能在可接受时间内跑完。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 生成不含相邻零的二进制字符串 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。