一、题目描述
给你一个正整数 n。
如果一个二进制字符串 x 的所有长度为 2 的
子字符串
中包含 至少 一个 “1”，则称 x 是一个 有效 字符串。
返回所有长度为 n 的 有效 字符串，可以以任意顺序排列。
示例 1：
输入： n = 3
输出： ["010","011","101","110","111"]
解释：
长度为 3 的有效字符串有：“010”、“011”、“101”、“110” 和 “111”。
二、解题思路
本题的目标就是找长度为n的2进制数，其中不能有两个0相连
这里我才用最简单的解法 回溯法 但这道题目还有速度更快的解法，位运算
回溯法过程：
字符串的每个位置都需要填入 0 或 1。对于 0≤i<n，如果 i=0 或字符串的下标 i−1 处填入 1，则字符串的下标 i 处可以填入 0 或 1，否则字符串的下标 i 处只能填入 1。
当得到一个长度为 n 的有效字符串时，我们可以判断这个字符串是否符合要求，如果符合要求则将该字符串添加到结果列表中。
三、代码
class Solution {
public:// 判断字符串是否符合条件bool check(string s){int size = s.size();for(int i=0;i<size;i++){if(s[i]=='0'&&s[i+1]=='0'){return false;}}return true;}vector<string> validStrings(int n) {vector<string> res;string cur = "";backtrack(cur,n,0,res);return res; }// 回溯法 void backtrack(string &cur,int n,int level,vector<string> &res){if(level> n){return;}if(level == n && check(cur)){res.push_back(cur);return;}cur.push_back('0');level++;backtrack(cur,n,level,res);cur.pop_back();cur.push_back('1');backtrack(cur,n,level,res);cur.pop_back();level--;}
};
