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.