[LeetCode | Python] 20. Valid Parentheses

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.Every close bracket has a corresponding open bracket of the same type.

괄호가 올바르게 짝지어졌는지 확인하는 문제!

 

풀이1: Stack 이용

class Solution:
    def isValid(self, s: str) -> 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

stack을 통해 열린 괄호를 저장하고, 닫힌 괄호가 나오면 스택의 마지막 요소와 짝이 맞는지 확인한다.

짝이 맞지 않으면 (}와 같이 잘못된 구조이므로 바로 False를 리턴하고, 짝이 맞으면 스택에서 제거한다.

문자열을 모두 확인한 후 stack이 비어있으면 True, 비어 있지 않으면 False를 리턴한다.

반복문을 한번 순회하므로 시간복잡도는 O(n)

 

풀이2: 브루트포스 (neetcode 풀이)

class Solution:
    def isValid(self, s: str) -> bool:
        while '()' in s or '{}' in s or '[]' in s:
            s = s.replace('()', '')
            s = s.replace('{}', '')
            s = s.replace('[]', '')
        return s == ''

생각하지 못한 풀이인데, 위와 같이 브루트포스로도 풀 수 있다.

연속되는 괄호쌍을 지속적으로 지워나가는 방법이다.

replace 연산이 O(n)이 걸리므로, 시간복잡도는 O(n^2)