LC20 Valid Parentheses

class Solution:
    def isValid(self, s: str) -> bool:
        """
        time O(N) space O(2N)
        step1, use a map to store opening parentheses as key and corresponding closing paretheese as val. initialize a stack
        step2, loop through s, check if stack empty
        step3, if empty, directly push ch into stack ,go to next loop
        step4, if not empty, check if ch in dictionary. 
        step5, if not, push into stack, if yes pop top stack and skip to next loop
        step6, after whole iteration complete, check if stack empty
        """
        d = {'(':')','[':']','{':'}'}
        stack = []
        for ch in s:
            if not stack:
                stack.append(ch)
                continue
                
            if ch == d.get(stack[-1]):
                stack.pop()
                continue
            else:
                stack.append(ch)
        return not stack
                    

class Solution:
    def isValid(self, s: str) -> bool:
        """
        time O(N) space O(N)
        main idea: internalize map. open parenteses will always appear first .each time meet a open parentheses, only push closing one. the moment when current ch is not open paretheses, element in the top(note we need to make sure stack is not empty) will be the same as current ch. otherwise it;s not valid. 
        """
        d = {'(':')','[':']','{':'}'}
        stack = []
        for ch in s:
            if ch == '(':
                stack.append(')')
            elif ch == '{':
                stack.append('}')
            elif ch == '[':
                stack.append(']')
            elif len(stack)== 0 or stack.pop() != ch:
                return False
        return len(stack) == 0

class Solution:
    def isValid(self, s: str) -> bool:
        st = []
        for c in s:
            if c in ['(','{','[']:
                st.append(c)
            elif c == ')' :
                if st and st[-1] == '(':
                    st.pop()
                else:
                    return False
            elif c == ']':
                if  st and st[-1] == '[':
                    st.pop()
                else:
                    return False
            elif c == '}' :
                if st and st[-1] == '{':
                    st.pop()
                else:
                    return False
        return False if st else True