aboutsummaryrefslogtreecommitdiff
path: root/generate_binary_string_without_adj_0.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-05-21 21:22:51 -0600
committerJack Sangdahl <[email protected]>2025-05-21 21:22:51 -0600
commit3bf84df609fdf9d975804ababe8aea617791f8b0 (patch)
tree0668bf6116c62cad3f81b3d669495027c87f1703 /generate_binary_string_without_adj_0.c
parent34314ef21ca6e4b6fbb812563c168d01aac36f09 (diff)
downloadleetcode-3bf84df609fdf9d975804ababe8aea617791f8b0.tar.gz
leetcode-3bf84df609fdf9d975804ababe8aea617791f8b0.zip
3211. generate binary strings without adjacent zeros
Diffstat (limited to 'generate_binary_string_without_adj_0.c')
-rw-r--r--generate_binary_string_without_adj_0.c55
1 files changed, 55 insertions, 0 deletions
diff --git a/generate_binary_string_without_adj_0.c b/generate_binary_string_without_adj_0.c
new file mode 100644
index 0000000..7ad3843
--- /dev/null
+++ b/generate_binary_string_without_adj_0.c
@@ -0,0 +1,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);
+}