3211. 生成不含相邻零的二进制字符串
INFO
每日一题 2024.10.24
md
给你一个正整数 n。
如果一个二进制字符串 x 的所有长度为 2 的子字符串中包含 至少 一个 "1"，则称 x 是一个 有效 字符串。
返回所有长度为 n 的 有效 字符串，可以以任意顺序排列。
示例 1：
输入： n = 3
输出： ["010","011","101","110","111"]
解释：
长度为 3 的有效字符串有："010"、"011"、"101"、"110" 和 "111"。
示例 2：
输入： n = 1
输出： ["0","1"]
解释：
长度为 1 的有效字符串有："0" 和 "1"。
提示：
1 <= n <= 18就是生成不含相邻零的二进制字符串。
go
/*
* @lc app=leetcode.cn id=3211 lang=golang
* @lcpr version=30204
*
* [3211] 生成不含相邻零的二进制字符串
*/
func validStrings(n int) []string {
// 子字符串是指一个字符串中的连续字符序列。换句话说，子字符串是从原字符串中提取的一段连续字符。
// 就是生成不含相邻零的二进制字符串。
// return一层的时候退一层
var result []string
var generate func(current string, remain int)
generate = func(current string, remain int) {
if remain == 0 {
result = append(result, current)
return
}
// 末尾为1的时候加0
if len(current) == 0 || current[len(current)-1] != '0' {
generate(current+"0", remain-1)
}
// 末尾为0的时候加1
// 保证没有相邻0就行
generate(current+"1", remain-1)
}
generate("", n)
return result
}