This content originally appeared on DEV Community and was authored by Kimita Kibana Wanjohi
First lets use a stack method.
I know what you are thinking, "but using a stack we will have O(n) space", yes. But first lets go through stack method for those who are not familiar with with this problem.
I'll be implementing this in python.
step 1 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 helpfull
Solving it.
first we start by creating a helper function to check if a pair of parentheses are a match, e.g. () this is a match, (} and this 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 main with this function is that it returns True if a pair matches and false if the pair don't match.
Before we code the solution we should first go through how it works and visualize it.
I'll write it in pseudo gibberish first.
Function (String containing brackets) # e.g "(({[]}))"
check if the string length is odd or even.
if odd return false. # since the parentheses come in pairs
initialize variables [index = 0, is_balanced = True, n = string_length]
Loop while index < n and is_balanced = True:
get the bracket in string using the index we are at.
if its an opening bracket:
push it to the stack.
else: # its a closing bracket
check if stack is empty:
if empty set is_balaced to false
else: # stack not empty
pop the top element in the stack and compare with the element at our index
if they are not a match:
set is_balanced to false
the increase the index with one.
check if the stack is empty and is_balanced is True:
return True
else:
False
Now this is the code
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 run time of this is O(n) time and O(n) space, note this is the best I found Online. But I have another way of solving this problem.
My solution
my method uses two pointers one at the beginning and the other at the end, then the two pointers work their way to the middle of the string, kinda 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, coz 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 O(1) space.
~ tilde is a bitwise operator NOT. this might help if you've never heard of it.
Thank you
This content originally appeared on DEV Community and was authored by Kimita Kibana Wanjohi
Kimita Kibana Wanjohi | Sciencx (2021-07-26T09:44:56+00:00) Checking if a pair of parentheses are balanced in O(n) time and O(1) Space.. Retrieved from https://www.scien.cx/2021/07/26/checking-if-a-pair-of-parentheses-are-balanced-in-on-time-and-o1-space/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.