2025-02-24：生成不含相邻零的二进制字符串。用go语言，给定一个正整数 n。

一个二进制字符串 x 被称为有效字符串，如果它的所有长度为 2 的子字符串中至少包含一个 “1”。

你的任务是返回所有长度为 n 的有效字符串，顺序可以任意。

1 <= n <= 18。

输入： n = 3。

输出： [“010”,“011”,“101”,“110”,“111”]。

解释：

长度为 3 的有效字符串有：“010”、“011”、“101”、“110” 和 “111”。

答案2025-02-24：

chatgpt

题目来自leetcode3211。

大体步骤如下：

1.初始化：开始时，我们先定义一个空数组 res 用于存储最终结果，然后确定一个长度为 n 的二进制字符串 temp，初始内容为空。

2.递归生成有效字符串：

• 定义一个递归函数，该函数接收一个当前位置 pos 和当前的二进制字符串 temp。

• 从当前位置 pos 开始，尝试添加 ‘0’ 和 ‘1’ 到当前的二进制字符串 temp，并检查是否生成的子串符合条件（不含相邻零）。

• 如果符合条件，继续递归调用函数，向下一个位置前进。

• 当递归到字符串长度为 n 时，将有效的二进制字符串存入 res 中。

3.回溯：

• 在递归结束后，回溯到上一个位置，尝试其他可能性，以生成所有有效的二进制字符串。

4.总的时间复杂度：

• 由于要生成所有长度为 n 的有效字符串，对于每个位置有两种选择，时间复杂度为 O(2^n)。

5.总的额外空间复杂度：

• 在递归过程中，需要保存当前的二进制字符串以及结果数组，额外空间为 O(2^n)。

综上所述，通过递归生成所有符合条件的二进制字符串，时间复杂度为 O(2^n)，额外空间复杂度为 O(2^n)。这种方法会枚举所有可能的二进制字符串，并检查它们是否符合条件。

Go完整代码如下：

package main

import (
	"fmt"
)

func validStrings(n int) []string {
	res := []string{}
	mask := (1 << n) - 1

	for i := 0; i < 1<<n; i++ {
		t := mask ^ i
		if t>>1&t == 0 {
			res = append(res, fmt.Sprintf("%0*b", n, i))
		}
	}

	return res
}

func main() {
	n := 3
	result := validStrings(n)
	fmt.Println(result)
}

Rust完整代码如下：

fn valid_strings(n: i32) -> Vec<String> {
    let mut res: Vec<String> = Vec::new();
    let mask = (1 << n) - 1;

    for i in 0..(1 << n) {
        let t = mask ^ i;
        if t >> 1 & t == 0 {
            res.push(format!("{:0width$b}", i, width = n as usize));
        }
    }

    res
}

fn main() {
    let n = 3;
    let result = valid_strings(n);
    println!("{:?}", result);
}

Python完整代码如下：

# -*-coding:utf-8-*-

def valid_strings(n):
    res = []
    mask = (1 << n) - 1

    for i in range(1 << n):
        t = mask ^ i
        if t >> 1 & t == 0:
            res.append(format(i, f'0{n}b'))

    return res

def main():
    n = 3
    result = valid_strings(n)
    print(result)

if __name__ == "__main__":
    main()