Approach #1 One Stack [Accepted]
Intuition
We can use concept of stack to emulate the process of checking valid parenthese.
Algorithm
 we create a list type for
stack
 iterate
s
 check whether the next character in
s
is left parenthese or not if yes, we append it into
stack
 if not, and if it is right parenthese, go to step 4.
 if not the above case, it is definitely invalid parenthese, so we have to
return False
 if yes, we append it into
 if the right parenthese is matching the left parenthese which is the last element in stack, we can
pop
thestack
.  after all, if no one left in
stack
, we can said this is valid parenthese.
Python
class Solution(object):
def isValid(self, s):
stack = []
for c in s:
if c == '(' or c == '[' or c == '{':
stack.append(c)
elif c == ')' and len(stack) > 0 and stack[1] == '(':
stack.pop()
elif c == '}' and len(stack) > 0 and stack[1] == '{':
stack.pop()
elif c == ']' and len(stack) > 0 and stack[1] == '[':
stack.pop()
else: # e.g. s = ']'
return False
return len(stack) == 0
Complexity Analysis
 Time complexity : $$O(n)$$.

Iterating through
s
for time complexity is $$O(len(s)) = O(n)$$. 
pop
,append
,len
of list operations are all $$O(1)$$.
 Space complexity : $$O(n)$$.
We need $$O(N)$$ space for stack
.
Approach #2 One stack and One Map [Accepted]
Intuition
Use one map
to avoid multiple if
conditions.
But it costs extra constant memory space.
Algorithm
 we have to create mapping for left and right parentheses
 iterate all character in string
 if stack is not empty and if that character is right parenthese
 we
pop
the stack to see whether two parentheses are match
 we
 if that character is left parenthese, all we need to do is
append
it tostack
.
 if stack is not empty and if that character is right parenthese
 after all, if stack is empty, it means all parenthese
pop
clearly, and we can claim that it is valid parenthese.
Python
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stack = []
right_to_left = {')':'(',']':'[','}':'{'}
for c in s:
if stack and c in right_to_left.keys(): # c is right parenthese
last_ele = stack.pop()
if last_ele != right_to_left[c]:
return False
# even if it is equal, we HAVE ALREADY poped it.
elif c in right_to_left.values(): # c is left parenthese
stack.append(c)
else: # c causes invalid parenthese e.g. s = ']'
return False
return stack == []
Complexity Analysis
 Time complexity : $$O(n)$$.

dict.keys()
,dict.values()
andin dict
are all $$O(1)$$. 
Iterating through
s
for time complexity is $$O(len(s)) = O(n)$$.
 Space complexity : $$O(n + 1)) = O(n)$$.
Although we have an additional dictionary type for mapping parenthese, it only costs constant memory space.