about summary refs log tree commit diff
path: root/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/valid-parens.py
diff options
context:
space:
mode:
authorVincent Ambo <mail@tazj.in>2021-12-13T22·51+0300
committerVincent Ambo <mail@tazj.in>2021-12-13T23·15+0300
commit019f8fd2113df4c5247c3969c60fd4f0e08f91f7 (patch)
tree76a857f61aa88f62a30e854651e8439db77fd0ea /users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/valid-parens.py
parent464bbcb15c09813172c79820bcf526bb10cf4208 (diff)
parent6123e976928ca3d8d93f0b2006b10b5f659eb74d (diff)
subtree(users/wpcarro): docking briefcase at '24f5a642' r/3226
git-subtree-dir: users/wpcarro
git-subtree-mainline: 464bbcb15c09813172c79820bcf526bb10cf4208
git-subtree-split: 24f5a642af3aa1627bbff977f0a101907a02c69f
Change-Id: I6105b3762b79126b3488359c95978cadb3efa789
Diffstat (limited to 'users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/valid-parens.py')
-rw-r--r--users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/valid-parens.py50
1 files changed, 50 insertions, 0 deletions
diff --git a/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/valid-parens.py b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/valid-parens.py
new file mode 100644
index 000000000000..56f2c0b27456
--- /dev/null
+++ b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/valid-parens.py
@@ -0,0 +1,50 @@
+def valid_parens(n):
+    if n == 0:
+        return []
+    if n == 1:
+        return ["()"]
+
+    result = set()
+    for x in valid_parens(n - 1):
+        result.add("({})".format(x))
+        result.add("(){}".format(x))
+        result.add("{}()".format(x))
+    return result
+
+def valid_parens_efficient(n):
+    result = []
+    curr = [''] * n**2
+    do_valid_parens_efficient(result, curr, 0, n, n)
+    return result
+
+def do_valid_parens_efficient(result, curr, i, lhs, rhs):
+    if lhs == 0 and rhs == 0:
+        result.append(''.join(curr))
+    else:
+        if lhs > 0:
+            curr[i] = '('
+            do_valid_parens_efficient(result, curr, i + 1, lhs - 1, rhs)
+        if rhs > lhs:
+            curr[i] = ')'
+            do_valid_parens_efficient(result, curr, i + 1, lhs, rhs - 1)
+
+# Avoids recursion by using either a stack or a queue. I think this version is
+# easier to understand.
+def valid_parens_efficient_2(n):
+    result = []
+    xs = []
+    xs.append(('', n, n))
+    while xs:
+        curr, lhs, rhs = xs.pop()
+        print(curr)
+        if lhs == 0 and rhs == 0:
+            result.append(''.join(curr))
+        if lhs > 0:
+            xs.append((curr + '(', lhs - 1, rhs))
+        if rhs > lhs:
+            xs.append((curr + ')', lhs, rhs - 1))
+    return result
+
+# print(valid_parens(4))
+print(valid_parens_efficient(3))
+print(valid_parens_efficient_2(3))