## DEV Community

Kimita Kibana Wanjohi

Posted on • Updated on

# First, let's use the stack method.

I know what you are thinking, "but using a stack will result in `O(n)` space." Yes, but first let's go through the stack method for those who are not familiar with this problem. I'll be implementing this in Python.

### Creating a stack

In Python, we can use a list to implement a stack.

``````class Stack():
def __init__(self):
self.items = []

def push(self, item):
self.items.append(item)

def pop(self):
return self.items.pop()

def is_empty(self):
return self.items == []

def get_stack(self):
return self.items

def peek(self):
if not self.is_empty():
return self.items[-1]
``````

If you are not familiar with stacks, you might find this helpful.

### Solving the balanced parenthesis problem

First, we start by creating a helper function to check if a pair of parentheses is a match, i.e., `()` is a match, `(}` is not.

``````def is_match(p1, p2):
if p1 == "(" and p2 == ")":
return True
elif p1 == "[" and p2 == "]":
return True
elif p1 == "{" and p2 == "}":
return True
else:
return False
``````

The above function takes a pair of parentheses as parameters `p1` and `p2` and checks if the two match.

### The main function

``````def balance_parens(paren_string):
stack = Stack()
index = 0
n = len(paren_string)
is_balanced = True

while index < n and is_balanced:
paren = paren_string[index]

if paren in "([{":
stack.push(paren)
else:
if stack.is_empty():
is_balanced = False
else:
top = stack.pop()
if not is_match(top, paren):
print(top, paren)
is_balanced = False
index += 1

if stack.is_empty() and is_balanced:
return True
else:
return False
``````

The runtime of this function is `O(n)` time and `O(n)` space.

### My solution

My method uses two pointers, one at the beginning and the other at the end of the string. Then the two pointers work their way to the middle of the string, kind of like attacking it from both ends, checking if the brackets are a match.

#### Cons

If it encounters a string like this `()(([]))`, it would return false even though this is balanced because index 1 and -2 don't match. Anyone has an idea on how we could solve that? Leave a comment.

### Code

``````def b_parens(paren_string):
n = len(paren_string)

if n % 2 != 0:
return False

n = n // 2

for i in range(n):
p1 = paren_string[i]
p2 = paren_string[~i]

if not is_match(p1, p2):
return False
return True
``````

Since we loop through the array once, the time complexity is `O(n)` and the space complexity is `O(1)`. The `~` tilde is a bitwise

operator NOT. This might help if you've never heard of it.

Thank you. 