• # Problems

For this solution, we only want to find those two situations:

1. If the current char is the back parenthesis: is it the corresponding parenthesis of last added parenthesis
2. If the current char is the front parenthesis: add it to our pending structure

# Solutions

• From the requirements above, we know using a `stack` is the best choice.

• How to relate the front parenthesis with back parenthesis?
We can use a `dictionary`, where the `keys` are the back parenthesis while the `values` are the front parenthesis.

• The pros of using a dict is determining whether element is a key or value only requires O(1) time complexity. `x in dic` and `x in dic.viewvalues()`

``````def isValid(self, s):
dic = {']' : '[', '}' : '{', ')' : '('}
stack = []
for char in s:
if char in dic.viewvalues():
stack.append(char)
elif char in dic:
if not stack or stack.pop() != dic[char]:
return False
return True if not stack else False``````

• I liked your solution but you can make things a bit shorter and clearer by noticing a few things:

1. There's no need to `elif char in dic` because by the assumptions of the question ("containing just the characters..." ) you know that if it's not an opening parentheses, it's a closing one.
2. While I know that `not stack` checks both for `None` and an empty list, I prefer `len(stack) == 0` as it's much clearer. (It's a question of taste but that's just my opinion)
3. Instead of `return True if not stack else False`, you can do: `return not stack` or `return len(stack) == 0`

Here's what I coded:

``````class Solution(object):
def isValid(self, s):
pairs, stack = {'[': ']', '{': '}', '(': ')'}, []
for char in s:
if char in pairs:
stack.append(char)
elif len(stack) == 0 or pairs[stack.pop()] != char:
return False
return len(stack) == 0
``````

• @nirnaor why do you need to check `len(stack) == 0` in the elif?

• @HammerKing Notice that you'll get to the `elif` part only when `char` is a close parantheses. Consider these two inputs that should return `False`:

1. `s =='(]'` : Returns `False` because `pairs[stack.pop()]` is `')'` which is not `']'`.
2. `s ==']'` : Returns `False` because no matching parantheses was inserted earlier to the stack, thus `len(stack) == 0`.

Without the first part, `stack.pop` would have raised an `IndexError`.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.