20. Valid Parentheses

20. Valid Parentheses

 

class Solution:
    def isValid(self, s: str) -> bool:
        # 닫힌 괄호를 키로 하고, 해당하는 열린 괄호를 값으로 가지는 딕셔너리
        parentheses = {')': '(', '}': '{', ']': '['}

        # 괄호를 추적하기 위한 스택 초기화
        stack = []

        # for i in range(len(s)):
        #     if s[i] in parentheses and len(stack) >0:
        #         if stack[-1] == parentheses[s[i]]:
        #             stack.pop()
        #         else:
        #             return False
        #     else:
        #         stack.append(s[i])
        # return len(stack) == 0

        # 문자열 s의 각 문자를 순회
        for c in s:
            # 닫힌 괄호인지 확인하고 스택이 비어 있지 않은 경우 처리
            if c in parentheses and len(stack) > 0:
                # 스택의 최상단 값(가장 최근의 열린 괄호)이 닫힌 괄호와 짝이 맞는지 확인
                if stack[-1] == parentheses[c]:
                    stack.pop()  # 짝이 맞으면 스택에서 최상단 값 제거
                else:
                    return False  # 짝이 맞지 않으면 유효하지 않은 문자열로 판단
            else:
                # 열린 괄호이거나, 스택이 비어있는 경우 스택에 추가
                stack.append(c)

        # 모든 문자를 처리한 후, 스택이 비어있다면 유효한 문자열
        return len(stack) == 0

 

https://youtu.be/WTzjTskDFMg?si=Pfn_fDQwzEFx4E3g

 

 

최종 코드 

 

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 stack == [] # return True if not stack else False

 

Time & Space Complexity

• Time complexity: O(n)
• Space complexity: O(n)

 

class Solution:
    def isValid(self, s: str) -> bool:
        # if len(s) < 2:
        #     return False
        # 위 조건은 없어도 됨. 빈 문자열도 유효한 괄호 문자열로 간주됨 ("") → True

        valid = {")": "(", "}": "{", "]": "["}  # 닫는 괄호를 key, 대응하는 여는 괄호를 value로 저장
        stack = []  # 여는 괄호들을 저장할 스택

        for ch in s:  # 문자열의 각 문자(ch)를 순회
            if ch not in valid:
                # 여는 괄호라면 스택에 넣기
                stack.append(ch)
            else:
                # 닫는 괄호인데 스택이 비어 있다면 → 짝이 없음
                if not stack:
                    return False

                # 스택에서 마지막 여는 괄호를 꺼냄
                bracket = stack.pop()

                # 꺼낸 괄호와 현재 닫는 괄호가 짝이 맞는지 확인
                if bracket != valid[ch]:
                    return False

        # 스택이 비어 있으면 모든 괄호가 짝을 이루었음 → 유효
        # 아직 남아 있는 여는 괄호가 있으면 → 유효하지 않음
        return True if not stack else False