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

思路

由于每个长度为2的子字符串都必须含一个1，所以如果前一个字符为‘0’的话下一个字符必须是‘1’，如果上一个字符是‘1’的话那么下一个字符填什么都可以，直接模拟这个过程写一个dfs即可

Solutions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<string> validStrings(int n) {
        vector<string> ans;
        string path(n, 0);
        auto dfs = [&](auto&& dfs, int i) -> void{
            if(i == n){
                ans.push_back(path);
                return;
            }
            path[i] = '1';
            dfs(dfs, i+1);
            if(i == 0 || path[i-1] == '1'){
                path[i] = '0';
                dfs(dfs, i+1);
            }
        };
        dfs(dfs, 0);
        return ans;
    }
};