Recently, I've solved the "Valid Parenthesis" problem on LeetCode:
Given a string containing just the characters
'('
,')'
,'{'
,'}'
,'['
and']'
, determine if the input string is valid.The brackets must close in the correct order,
"()"
and"()[]{}"
are all valid but"(]"
and"([)]"
are not.
I've decided to iterate over every character in the string and push it on stack if it is an opening bracket. If not, pop from the stack and check if the closing bracket matches the opening bracket.
Here is my implementation:
OPENING_BRACKETS = {"{", "[", "("}
BRACKETS_MAP = {"]": "[", "}": "{", ")": "("}
class Solution(object):
def isValid(self, s):
if not s: # empty string is a valid string
return True
if s[0] not in OPENING_BRACKETS:
return False # early exit if string does not start with an opening bracket
stack = []
for index, bracket in enumerate(s):
if bracket in OPENING_BRACKETS:
stack.append(bracket)
else:
try:
last_opening_bracket = stack.pop()
if last_opening_bracket != BRACKETS_MAP[bracket]: # last closing bracket does not match last opening bracket
return False
except IndexError:
return False # pop from an empty stack means the brackets are not balanced
return not stack # if something left on stack, brackets are unbalanced
Is it the most optimal approach to solving the problem Time- and Space- Complexity wise? What would you suggest to improve in the presented solution?