题目描述
思路解析动画文字版
记牢这套口诀:填 1 随便填,填 0 先看上一位,填满就收,走到头就回退换下一种。下面每一帧都在套它,舞台上方是这一位的两个候选,中间是正在拼的串 path,下面是已经收下的合法串。
先看舞台。上面「可选数字」是每一位的两个候选,填 0 或者填 1;中间 path 是正在拼的串,现在还是空的;下面 res 收集所有拼满且合法的串。我们从第 1 位开始,先试着填 0。
第 1 位填 0,这是第一位,前面没有别的位,填 0 安全。现在 path 是 0,往下钻去定第 2 位。
走到第 2 位,想填 0,先看上一位。上一位是 0,要是这位再填 0,就凑出了连续两个 0,违反规则。所以把候选里的 0 划掉,这一位不能填 0,只能改填 1。
第 2 位填 1,现在 path 是 01。填 1 永远安全,不用检查。往下钻,去定第 3 位。
第 3 位填 0,上一位是 1,不会出现 00,凑齐了长度 3。这一串 010 合法,收进结果,现在已经收了 1 个。
这条路拼满了,把末位的 0 收回来,path 退回 01,回到上一位换下一种填法。这就是回溯:退一步,才好探另一条路。
第 3 位填 1,凑齐了长度 3。1 不会和前面凑成 00,这一串 011 合法,收进结果,现在已经收了 2 个。
这条路拼满了,把末位的 1 收回来,path 退回 01,回到上一位换下一种填法。这就是回溯:退一步,才好探另一条路。
这条路能试的都试过了,把末位的 1 收回来,path 退回 0,回到上一位换下一种填法。这就是回溯:退一步,才好探另一条路。
这条路能试的都试过了,把末位的 0 收回来,path 退回 空,回到上一位换下一种填法。这就是回溯:退一步,才好探另一条路。
第 1 位填 1,现在 path 是 1。填 1 永远安全,不用检查。往下钻,去定第 2 位。
第 2 位填 0,上一位是 1,填 0 不会出现 00。现在 path 是 10,往下钻去定第 3 位。
走到第 3 位,想填 0,先看上一位。上一位是 0,要是这位再填 0,就凑出了连续两个 0,违反规则。所以把候选里的 0 划掉,这一位不能填 0,只能改填 1。
第 3 位填 1,凑齐了长度 3。1 不会和前面凑成 00,这一串 101 合法,收进结果,现在已经收了 3 个。
这条路拼满了,把末位的 1 收回来,path 退回 10,回到上一位换下一种填法。这就是回溯:退一步,才好探另一条路。
这条路能试的都试过了,把末位的 0 收回来,path 退回 1,回到上一位换下一种填法。这就是回溯:退一步,才好探另一条路。
第 2 位填 1,现在 path 是 11。填 1 永远安全,不用检查。往下钻,去定第 3 位。
第 3 位填 0,上一位是 1,不会出现 00,凑齐了长度 3。这一串 110 合法,收进结果,现在已经收了 4 个。
这条路拼满了,把末位的 0 收回来,path 退回 11,回到上一位换下一种填法。这就是回溯:退一步,才好探另一条路。
第 3 位填 1,凑齐了长度 3。1 不会和前面凑成 00,这一串 111 合法,收进结果,现在已经收了 5 个。
这条路拼满了,把末位的 1 收回来,path 退回 11,回到上一位换下一种填法。这就是回溯:退一步,才好探另一条路。
这条路能试的都试过了,把末位的 1 收回来,path 退回 1,回到上一位换下一种填法。这就是回溯:退一步,才好探另一条路。
这条路能试的都试过了,把末位的 1 收回来,path 退回 空,回到上一位换下一种填法。这就是回溯:退一步,才好探另一条路。
所有分支都搜遍了,右边正好收了 5 个合法串:010、011、101、110、111。它们的共同点是任意相邻两位都不同时为 0。这就是 n 等于 3 的答案,一个不多一个不少。
边界手算:n 等于 1 时两个都要、n 等于 2 时只砍掉 00 剩三个、n 等于 3 时剩五个,数量正好是斐波那契的 2、3、5。
面试重点:逐位试填加上填 0 的约束、可换递推但仍要枚举、时间指数级所以 n 限制在 18。
参考代码
from __future__ import annotationsfrom 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 = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass 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复杂度
- 时间：O(n · 2^n)，上界是长度 n 的二进制串一共 2 的 n 次方个,回溯会把不合法的分支提前剪掉,实际有效串数是斐波那契级别、约 φ 的 n 次方(φ 约 1.618),每收一个串复制一次要 O(n)。所以时间随 n 指数增长,题目把 n 限制在 18 以内正是因为结果本身就是指数量级
- 空间：O(n)，按峰值算,不计输出本身。递归最深就是 n 层,path 最长也是 n 个字符,两者都是 O(n)。收集到的所有结果串是必须返回的输出,一般不计入额外空间
易错点
面试追问把动画讲成自己的话
追问这题的核心思路是什么?
追问除了回溯,还有别的做法吗?
追问为什么时间是指数级,n 却只到 18?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
解数独
LeetCode 37 · 困难 · 沿着 回溯套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题