20. Valid Parentheses

# Easy

知道就是知道，不知道就是不知道

Store (open_braket, close_braket) pair in mapping, to match each braket.

Use stack to ensure correct order, if it's an open braket, then add to stack, if it's a close braket, then pop out from stack.

Two true-false check:

1. check if stack is empty, then can't check last element of stack with new coming element.

2. check if stack is empty at the end, which means must ensure all open braket are closed.

Python

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        # edge case
        if len(s)%2 != 0: # odd, then must be false
            return False
        
        # regular case
        dic = {'(': ')', '[': ']', '{': '}'}
        left = set(['(', '[', '{'])
        stack = []
        for item in s:
            if item in left:
                stack.append(item)
            elif stack and item == dic[stack[-1]]:
                stack.pop()
            else:
                return False
            
        return stack == []

Time complexity = $O(n)$ , space comlexity = $O(n)$