leetcode-stack

20. Valid Parentheses.py

class Solution:
    """
    Thought Porcess:
        stack:
            Idea is use a stack to maintain all the open Parentheses on the left side of s[i].
            And top of stack is closest open Parentheses
            
            We traverse the given string forward.
                when encounter the open parenthese, we append the index
                when encounter the close parenthese, 
                    if stack is empty, means it must be invalid parenthese
                        (()) )...

                    else:
                        # to balance the unmatched open parenthese
                        # use a removed_index hashset to store the index needed to be removed
                        stack.pop()
                In the end, if our stack is not empty, means there's no enough close parenthese to match them, so return False.
        
        Idea is we would like to scan string in one time from left to right.
        If it's open parentheses, we need a container to store the most recent opening parathenese we traversed so far. In order to check if it's matched or not, when meeting closed parentheses.
        
        And this container should be stack, becausue it provide poping out most recent object in O(1)
    """
    open_parentheses = "({["
    close_parentheses = ")}]"
    def isValid(self, s: str) -> bool:
        """
        T:O(n)  because we simply traverse the given string one character at a time and push and pop operations on a stack take O(1)O(1) time.
        S:O(n)
        """
        n = len(s)
        stack = collections.deque([])
        for i in range(n):
            char = s[i]
            if char in self.open_parentheses:
                stack.append(char)
            elif char in self.close_parentheses:
                if len(stack) == 0:
                    return False
                else:
                    recent_open_parentheses = stack.pop()
                    if not self._match(recent_open_parentheses, char):
                        return False
            else:
                raise ValueError(f"invalid input :{s}")
        # 最後確認stack
        if len(stack) != 0:
            return False
        return True
    
    def _match(self, open_char, close_char):
        if self.open_parentheses.index(open_char)==self.close_parentheses.index(close_char):
            return True
        else:
            return False