**Solution**

**Stack Based Solution**

- Build a comparison dictionary for opening and closing brackets.
- Initialize a stack, We will only add opening brackets into this stack. The closing brackets will not be added but will be tested as the algorithm proceeds.
- If element is ")", "]", "}" and st is empty or stack's top is not a matching bracket, then return False
- If element is ")", "]", "}" and st is not empty or stack's top is a matching bracket, then pop from stack
- If element is "(", "[", "{", then add to stack.
- If there are any remaining elements in the stack, return False otherwise return True.

```
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
comp = {
')':'(',
']':'[',
'}':'{'
}
st = []
for x in s:
if x in (')', ']', '}'):
if len(st) == 0 or st[-1] != comp[x]:
return False
else:
st.pop()
else:
st.append(x)
return len(st) == 0
```

**Another version of this problem**

What if we just had a single bracket like "(" or ")"?

- The counter will increase when it is ‘(‘ and decrease when it is ‘)’. Whenever the counter is negative, we have more ‘)’ than ‘(‘ in the prefix which indicates an invalid input.