# 20. Valid Parentheses

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

An input string is valid if:

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

Example 1:

```Input: s = "()"
Output: true
```

Example 2:

```Input: s = "()[]{}"
Output: true
```

Example 3:

```Input: s = "(]"
Output: false
```

Example 4:

```Input: s = "([)]"
Output: false
```

Example 5:

```Input: s = "{[]}"
Output: true
```

Constraints:

• `1 <= s.length <= 104`
• `s` consists of parentheses only `'()[]{}'`.

Solution；

``````def isValid(self, s: str) -> bool:
dic = {'(':1 , ')':2 , '[':3 , ']':6 , '{':5 , '}':10}
res = []
for one in s:
temp = dic[one]
if(temp %2 ):
res.append(temp)
else:
if(len(res) and res[-1]==temp//2):
del res[-1]
else:
return False
return res==[]
``````

use `temp = dic[one]` to replace calculate `dic[one]` many times, it save many times . It can Improve 79% to 97
% beat times.

Runtime: 24 ms, faster than 97.46% of Python3 online submissions for Valid Parentheses.
Memory Usage: 12.9 MB, less than 100.00% of Python3 online submissions for Valid Parentheses.

Solution2:

``````def isValid(self, s: str) -> bool:
stack = []
left = set('([{')
right = set(')]}')
check = {')':'(', ']':'[', '}':'{'}
for i in s:
if i in left:
stack.append(i)
if i in right:
if not stack:
return False
elif stack.pop() != check[i]:
return False
else:
continue
if not stack:
return True
else:
return False
``````

”’

• Python solution with hash table and stack
• We go through the ‘string’ with one pass, so the time complexity would be O(n), spack complexity would be O(n).
• Each time when element i is in left, we append it into stack. And each time when element is in right, we compare stack.pop() with the counterpart in hash table until we return False when we find the mismatch or we return True when stack is empty and one pass is done.
Scroll to Top