aboutsummaryrefslogtreecommitdiff
path: root/generate_binary_string_without_adj_0.py
diff options
context:
space:
mode:
Diffstat (limited to 'generate_binary_string_without_adj_0.py')
-rw-r--r--generate_binary_string_without_adj_0.py36
1 files changed, 36 insertions, 0 deletions
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))