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.
Top comments (1)
Just count I guess. +1 for every opening parentheses, -1 for every closeing one. Balance should always be >= 0, otherwise ")(" would be legal, and in the end, balance=0. Different counters for different types of parens.
If "([)]" is illegal then it's more complicated.