20. Valid Parentheses (String, Stack)

링크 - https://leetcode.com/problems/valid-parentheses/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Easy

Intuition

이 문제는 stack을 통해 쉽게 풀 수 있다. 먼저 pairs를 통해 매칭되는 pair들을 미리 저장해놓는다. 그다음 s를 for문으로 돌면서 open인 것들은 stack에 넣고, 아니면 stack에서 pop해서 pair가 맞는지 확인한다. 마지막에 stack이 비어져 있어야 valid parentheses이다.

Code

class Solution:
    def isValid(self, s: str) -> bool:
        pairs = {
            ')': '(',
            '}': '{',
            ']': '['
        }

        stack = []
        for c in s:
            if c in pairs.keys():
                if not stack or stack.pop() != pairs[c]:
                    return False
            else:
                stack.append(c)
        return True if not stack else False

Complexity

Time Complexity: O(n) s를 다 돌아야 한다.

Space Complexity: O(n) stack에는 최대 n개의 원소들이 들어있게 된다(open된 것들만 있을 시)