Leetcode每日一题C之3211. 生成不含相邻零的二进制字符串

1、执行结果：通过

2、显示详情：

3、题目：  

给你一个正整数 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

4、思路：

可以用递归的方法来生成所有的二进制字符串并检查它们是否符合条件（所有长度为 2 的子字符串中包含 至少 一个 "1"），调用 generateStrings递归地生成所有有效的字符串，索引index为n时返回并将count加1，得到结果字符串的第一个字符串，直到输出所有的字符串。

1、当 index 为 0 时，可以选择 0 或 1 作为起始字符。选择0，有if(index ==0 || current[index-1]== '1')，选择1，if语句后面有 current[index] = '1';

2、如果前一个字符为 '1'，则可以选择 0 或 1 作为当前字符。

3、如果前一个字符为 '0'，则只能选择 '1'，以确保所有长度为 2 的子字符串中包含至少一个 '1' 

代码如下：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void generateString(char* current,int index,int n,char** result,int* count){
    if(index==n){
        result[*count]=(char*)malloc((n+1)*sizeof(char));
        strcpy(result[*count],current);
        (*count) ++;
        return ;
    }
    if(index ==0 || current[index-1]== '1'){
        current[index] = '0';
        generateString(current, index + 1, n, result, count);

    }
    current[index] = '1';
    generateString(current, index + 1, n, result, count);

}

char** validStrings(int n, int* returnSize) {
    int count=0;
    char** result = (char**)malloc( (1<<n)* sizeof(char*));
    char* current = (char*)malloc( (n+1) * sizeof(char));
    current[n] = '\0';
    generateString(current,0,n,result,&count);
    free(current);
    *returnSize = count;
    return result;  
}