The idea is to use stack operation to do the match. Traverse the string from left to right: if a left half parenthesis encountered, we push its right half to the stack; if a right half encountered, we compare it with stack top (they should be the same. Otherwise, the string is not valid) and pop the stack. After the traverse, the stack should be null (otherwise the string is not valid).

```
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
n = len(s)
D_match = {'(':')', '[':']', '{':'}'}
D_left = {'(':True, '[':True, '{':True, ')':False, ']':False, '}':False}
stack = []
for i in range(n):
if D_left[s[i]]==True: # if current char is a left half, append its right half to stack
stack.append(D_match[s[i]])
else: # if current char is a right half, compare it with stack top
if len(stack) > 0 and stack[-1] == s[i]:
stack.pop()
else:
return False
if len(stack) == 0:
return True
else:
return False
```