diff options
author | Jack Sangdahl <[email protected]> | 2025-05-21 21:22:51 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-05-21 21:22:51 -0600 |
commit | 3bf84df609fdf9d975804ababe8aea617791f8b0 (patch) | |
tree | 0668bf6116c62cad3f81b3d669495027c87f1703 | |
parent | 34314ef21ca6e4b6fbb812563c168d01aac36f09 (diff) | |
download | leetcode-3bf84df609fdf9d975804ababe8aea617791f8b0.tar.gz leetcode-3bf84df609fdf9d975804ababe8aea617791f8b0.zip |
3211. generate binary strings without adjacent zeros
-rw-r--r-- | generate_binary_string_without_adj_0.c | 55 | ||||
-rw-r--r-- | generate_binary_string_without_adj_0.py | 36 |
2 files changed, 91 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); +} diff --git a/generate_binary_string_without_adj_0.py b/generate_binary_string_without_adj_0.py new file mode 100644 index 0000000..5669156 --- /dev/null +++ b/generate_binary_string_without_adj_0.py @@ -0,0 +1,36 @@ +# 3211. Generate Binary Strings Without Adjacent Zeros + +""" +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. +""" + + +class Solution(object): + def __init__(self): + self.ans = [] + + def dfs(self, prev, str, n): + if len(str) == n: + self.ans.append(str) + return + self.dfs(1, str + "1", n) + if prev == 1: + self.dfs(0, str + "0", n) + + def validStrings(self, n): + """ + :type n: int + :rtype: List[str] + """ + self.ans = [] + self.dfs(0, "0", n) + self.dfs(1, "1", n) + return self.ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.validStrings(n=3)) + print(obj.validStrings(n=1)) |