An Interest In:
Web News this Week
- April 1, 2024
- March 31, 2024
- March 30, 2024
- March 29, 2024
- March 28, 2024
- March 27, 2024
- March 26, 2024
Some of Our Sources
- BoingBoing
- Simplebits
- Web Designer Wall
- Smashing Apps
- Abduzeedo
- You The Designer
- Noupe
- Web Design Ledger
- 24 Ways
- Android Dissected
Help Webnuz
Referal links:
Checking if a pair of parentheses are balanced in O(n) time and O(1) Space.
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 FalseThe 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 Trueelse: FalseNow 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 FalseThe 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 TrueSince 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
Original Link: https://dev.to/k2code/checking-if-a-pair-of-parentheses-are-balanced-in-o-n-time-and-o-1-space-17k8
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To