3211. 生成不含相邻零的二进制字符串

🎯 问题描述（来源于LeetCode）

描述：
给定一个正整数 n，请你返回所有长度为 n 的二进制字符串，且字符串中不包含两个连续的 0。
可以按任意顺序返回答案。

说明：

  • 字符串由字符 '0' 和 '1' 组成。
  • 不允许出现子串 "00"。

示例：

  • 示例 1：
1
2
3
输入: n = 3
输出: ["010","011","101","110","111"]
解释: 所有长度为3不含"00"的二进制字符串。
  • 示例 2：
1
2
输入: n = 1
输出: ["0","1"]

💻 解题思路

思路：回溯法（DFS） + 剪枝

算法步骤

  1. 初始化结果列表 ans 和长度为 n 的路径列表 path。
  2. 定义递归函数 dfs(i)，表示当前正在确定第 i 个字符（0‑indexed）：
    • 如果 i == n，将 path 拼接成字符串加入 ans 并返回。
    • 首先尝试放置 '1'（因为 '1' 永远不会产生连续的 0）：path[i] = '1'，递归 dfs(i+1)。
    • 然后尝试放置 '0'：仅当可以放置 '0' 时才进行。放置 '0' 的条件是：i == 0（第一个字符可以放 '0'）或者前一个字符 path[i-1] == '1'（确保不会出现 "00"）。若满足条件，则 path[i] = '0'，递归 dfs(i+1)。
  3. 从 dfs(0) 开始搜索。
  4. 返回 ans。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from typing import List

class Solution:
    def validStrings(self, n: int) -> List[str]:
        ans = []
        path = [""] * n

        def dfs(i):
            if i == n:
                ans.append("".join(path))
                return
            path[i] = "1"
            dfs(i+1)

            if i == 0 or path[i-1] == "1":
                path[i] = "0"
                dfs(i+1)

        dfs(0)
        return ans

📊 性能分析

  • 时间复杂度：O(2n)O(2^n)，但实际有效字符串数量约为斐波那契数 Fn+2F_{n+2}，因此远小于 2n2^n。对于 n ≤ 20 可高效运行。
  • 空间复杂度：O(n)O(n)，递归栈深度和路径存储。

思考

该解法通过回溯逐位构建字符串，利用规则“不能有两个连续 0”进行剪枝：只有当上一个字符是 '1' 或者是开头时，才允许放置 '0'。
优点：

  • 代码简洁，逻辑清晰，没有使用额外的集合或标记数组。
  • 剪枝条件直接有效，避免了无效分支的递归。