# 20. Valid Parentheses

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

So, in an essense, we need to match a left bracket with the correct right bracket and leave no open left bracket in the end.

# Stack

If we see a right bracket, it must match with the most recent left bracket. This logic leads us to use stack, which has FIFO.

``````    def isValid(self, s):
"""
:type s: str
:rtype: bool
use a stack

"""
left_side = ('(', '[', '{')
match = {'(':')', '[':']', '{':'}'}
stack = []

for brack in s:
if brack in left_side:
stack.append(brack)
else:
if not stack:
return False
poped = stack.pop()
if match[poped] != brack:
return False

if stack:
return False
return True
``````

# How to make it faster

## Remove the left list and use dictionary only

Use dictionary both for matching and check if the current bracket is a left bracket.

## Early termination

### Odd length

If the length of the bracket list is odd, then we know it is impossible to match successfully so we return False.

### Shrink if into one statement

``````    def isValid(self, s):
"""
:type s: str
:rtype: bool
use a stack

"""

match = {'(':')', '[':']', '{':'}'}
stack = []

for brack in s:
if brack in match:
stack.append(brack)
else:
if not stack or match[stack.pop()] != brack:
return False

return stack == []
``````

Move poping stack and checking if the poped element matches into same line will shorten the code.
Same with the last if statement that return false if the stack is not empty(which means we have unmatched left bracket).

Posted on Categories Leetcode