From 3bf84df609fdf9d975804ababe8aea617791f8b0 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Wed, 21 May 2025 21:22:51 -0600 Subject: 3211. generate binary strings without adjacent zeros --- generate_binary_string_without_adj_0.py | 36 +++++++++++++++++++++++++++++++++ 1 file changed, 36 insertions(+) create mode 100644 generate_binary_string_without_adj_0.py (limited to 'generate_binary_string_without_adj_0.py') 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)) -- cgit v1.2.3