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

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

给你一个正整数 n。

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

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

思路：所有长度为2的子字符串都包含1，也就是说，所有子字符串都不会存在相邻的两个0。
使用dfs来对答案进行搜索，并根据前一个位置是否存在，是否为1，来防止当前位置的元素，最后把长度为n的符合要求的字符串添加到结果中。

class Solution {
public:
    vector<string> validStrings(int n) {
    	// 记录满足要求的结果
        vector<string> ans;
		
		// dfs 函数，搜索答案
        function<void(int, string)> dfs = [&](int i, string str) {
        	// 如果 下标==n，代表当前字符串长度为n，加入答案数组，并终止该分支执行
            if (i == n) {
                ans.push_back(str);
                return ;
            }

			// 如果当前为第一个元素，则有两种添加方式，1 或 0
            if (str.size() == 0) {
                str += '0';
                // 递归
                dfs(i + 1, str);
                // 回溯
                str.pop_back();

                str += '1';
                dfs(i + 1, str);
                str.pop_back();
            } else {
            	// 如果当前不为第一个元素，且 str 中最后一个元素为 1，当前位置才可以放 0
                if (str.back() == '1') {
                    str += '0';
                    dfs(i + 1, str);
                    str.pop_back();
                }
                // 当前不为第一个元素，可以直接放 1
                str += '1';
                dfs(i + 1, str);
                str.pop_back();
            }
        };
        
		// 开始进行 dfs 搜索，初始时，下表为 0，字符串为""
        dfs(0, "");

        return ans;
    }
};