提示：本题可以可以利用递归或动态规划的方法。

---

一、问题描述

给定一个正整数 n，要求返回所有长度为 n 的二进制字符串，这些字符串满足条件：任意长度为 2 的子字符串中至少有一个字符是 “1”。
换句话说，不能出现连续的 “00”，这意味着我们必须确保在构建字符串时，“0” 后面不能再接 “0”。

示例

示例一：

输入: n = 3
输出: ["010", "011", "101", "110", "111"]
解释：所有符合要求的长度为 3 的有效字符串为 "010"、"011"、"101"、"110" 和 "111"。

---

示例二

输入: n = 1
输出: ["0", "1"]
解释：长度为 1 的字符串无论是 "0" 还是 "1"，都符合题目要求。

---

二、解题思路

我们要生成长度为 n 的二进制字符串，并确保所有长度为 2 的子字符串至少包含一个 “1”。为了解决这个问题，我们可以利用递归或动态规划的方法，逐步构造长度为 n 的有效字符串。

我们来分解问题，观察模式：

1，以 “1” 结尾的字符串没有任何限制，它可以接 “0” 或 “1”。例如，如果当前字符串是 “11”，我们可以生成 “110” 或 “111”。
2，以 “0” 结尾的字符串不能再接 “0”，因为不能出现 “00” 的情况。因此，唯一的选择是后面接 “1”。例如，如果当前字符串是 “10”，我们只能生成 “101”。

基于上述观察，我们可以递归构造出所有长度为 n 的有效字符串。

递归方法的想法：
从长度为 1 开始构造。
如果当前字符串的最后一个字符是 “1”，可以接 “0” 或 “1”。
如果当前字符串的最后一个字符是 “0”，只能接 “1”。
递归构造每个可能的组合，直到字符串长度达到 n。

三、代码实现

我们使用递归构造每一层的有效字符串，动态生成长度为 n 的结果。

class Solution:
    def generateValidBinaryStrings(self, n: int):
        # 初始化 base 情况
        if n == 1:
            return ["0", "1"]
        
        # 初始化 dp 数组，dp[i] 保存所有长度为 i 的有效字符串
        dp = [["0", "1"]]
        
        for i in range(2, n + 1):
            valid_strings = []
            for s in dp[-1]:  # 遍历上一层的字符串
                if s[-1] == '1':
                    # 如果前一个字符是 '1'，可以接 '0' 或 '1'
                    valid_strings.append(s + '0')
                    valid_strings.append(s + '1')
                else:
                    # 如果前一个字符是 '0'，只能接 '1'
                    valid_strings.append(s + '1')
            dp.append(valid_strings)
        
        return dp[-1]

# 测试
solution = Solution()
print(solution.generateValidBinaryStrings(3))  # 输出 ["010", "011", "101", "110", "111"]
print(solution.generateValidBinaryStrings(1))  # 输出 ["0", "1"]

代码解释

1.初始化基础情况：
如果 n = 1，二进制字符串只能是 “0” 或 “1”，这是我们递归的初始条件。

2.动态规划思想：
定义 dp[i] 来存储长度为 i 的所有有效字符串。
对于每个长度 i，从前一个长度的有效字符串构造当前长度的字符串。

3.构造逻辑：
遍历上一个长度的所有字符串 s：
如果字符串 s 以 “1” 结尾，可以在末尾添加 “0” 或 “1”。
如果字符串 s 以 “0” 结尾，则只能在末尾添加 “1”。

4.返回结果：
最终，dp[-1] 保存的是长度为 n 的所有有效字符串。

---

示例解释

以 n = 3 为例，解释代码的运行：

初始条件：长度为 1 的有效字符串是 [“0”, “1”]。

---

生成长度为 2 的字符串：
从 “0” 出发，只能生成 “01”。
从 “1” 出发，可以生成 “10” 和 “11”。
所以长度为 2 的有效字符串是 [“01”, “10”, “11”]。

---

生成长度为 3 的字符串：
从 “01” 出发，只能生成 “011”。
从 “10” 出发，可以生成 “101”。
从 “11” 出发，可以生成 “110” 和 “111”。
所以长度为 3 的有效字符串是 [“010”, “011”, “101”, “110”, “111”]。

四、总结

1.时间复杂度：每次递推生成长度为 n 的有效字符串时，递归地遍历前一层的结果。生成的有效字符串个数随 n 增长呈指数级，时间复杂度为O（2ⁿ），因为对于每个字符串，我们最多有两个选择。

2.空间复杂度：我们需要存储每一层的结果，空间复杂度也是O（2ⁿ） 。

---

虽然时间复杂度和空间复杂度都为指数级，但由于题目中 n 的范围是 1 到 18，这种复杂度是可以接受的。在最坏情况下，我们最多生成 2¹⁸个字符串，即 262144 个，计算量不算过大。