1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
// 3211. Generate Binary Strings Without Adjacent Zeros
#include "leetcode.h"
/*
* you are given a positive integer 'n'. a binary string 'x' is valid if all
* substrings of 'x' of length 2 contain at least one 1. return all valid
* strings with length 'n' in any order.
*/
void dfs(char **ans, int *returnSize, char *tmp, int *tmp_idx, int n,
bool prev) {
if ((*tmp_idx) == n) {
ans[(*returnSize)] = (char *)calloc(n + 1, sizeof(char));
memcpy(ans[(*returnSize)++], tmp, (*tmp_idx) * sizeof(char));
return;
}
if (prev) {
tmp[(*tmp_idx)++] = '1';
dfs(ans, returnSize, tmp, tmp_idx, n, !prev);
(*tmp_idx)--;
} else {
for (int i = 0; i < 2; i++) {
tmp[(*tmp_idx)++] = i + '0';
dfs(ans, returnSize, tmp, tmp_idx, n, !i);
(*tmp_idx)--;
}
}
}
char **validStrings(int n, int *returnSize) {
*returnSize = 0;
char **ans = (char **)malloc(pow(2, n) * sizeof(char *));
char *tmp = (char *)calloc(n + 1, sizeof(char));
for (int i = 0; i < 2; i++) {
int tmp_idx = 0;
tmp[tmp_idx++] = i + '0';
dfs(ans, returnSize, tmp, &tmp_idx, n, !i);
}
free(tmp);
return ans;
}
int main() {
int rs1, rs2;
char **vs1 = validStrings(3, &rs1);
char **vs2 = validStrings(1, &rs2);
for (int i = 0; i < rs1; i++)
printf("%s ", vs1[i]); // expect: ["010","011","101","110","111"]
printf("\n");
for (int i = 0; i < rs1; i++)
printf("%s ", vs2[i]); // expect: ["0","1"]
printf("\n");
free(vs1);
free(vs2);
}
|