20. Valid Parentheses

---

Problem

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

• Open brackets must be closed by the same type of brackets.
• Open brackets must be closed in the correct order.

Example

Solution

class Solution:
    def isValid(self, s: str) -> bool:
        table = {
            '}' : '{',
            ']' : '[',
            ')' : '('
        }
        stack = []
        
        # 예외 처리및 스택으로 이용하여 일치하는지 여부 판별
        for char in s:
            if char not in table:
                stack.append(char)
            elif not stack or table[char] != stack.pop():
                return False
        return len(stack) == 0

Runtime : 28 ms

• 열린 괄호 ( (, [, {) 들은 스택에 푸쉬하고 닫힌 괄호들 ( ), ], } )을 만날때마다 스택에서 pop()한 결과가 매칭되는지 확인하여 맞으면 True 아니면 False를 리턴하는 풀이 방법이다.

• Python 리스트는 스택 연산인 push와 pop이 O(1)에 동작하기 때문에 성능에도 큰 문제가 없다.

파이썬 알고리즘 인터뷰 - 박상길 참고