Valid Parentheses

https://leetcode.com/problems/valid-parentheses/

Prerequisite Hash Map Stack

最初にどのカッコがどの括弧閉じにマッチしているかわかるために HashMap を作る必要がある。この際、括弧閉じをキーにする。

for 文で list の中を確認し、括弧開きは stack に入れる。

stack は最後に入れたものから出すので、括弧開きと括弧閉じがマッチしていれば、 stack から pop できる。

最後に stack に何も残らなければ、全てがマッチして True を return する。

Time complexity: O(n) Mem complexity: O(n)

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        closeToOpen = { ')' : '(', ']' : '[', '}' : '{' }

        for c in s:
            if c in closeToOpen:
                if stack and stack[-1] == closeToOpen[c]:
                    stack.pop()
                else:
                    return False
            else:
                stack.append(c)
        
        return True if not stack else False