LeetCode: Valid Parentheses

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

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

 

Example 1:

Input: s = "()"

Output: true

Example 2:

Input: s = "()[]{}"

Output: true

Example 3:

Input: s = "(]"

Output: false

Example 4:

Input: s = "([])"

Output: true

 

Constraints:

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

 

이 문제는 생각보다 아이디어를 도출해내기 어려웠던 문제이다.

 

일단 문제에서 괄호를 열고 닫는 과정을 올바르게 한 string에 대해 true를 아니면 false를 반환해야 한다.

 

이 문제를 풀려면 괄호를 여닫는 행위의 정의를 해야한다. 

 

괄호를 올바르게 열고 닫는 행위를 논리적으로 생각해보자

 

가장 최근 괄호가 여는 부분일때, 닫는 부분이 들어온다면  닫는 문자와 최근 문자가 pair여야 한다.

 

가장 최근 괄호가 닫는 부분일 때, 여는 부분이 들어온다면 상관이 없다.  (이전까지의 값이 올바르다 생각)

 

가장 최근 값을 확인하기에 효율적인 스택을 활용해서 문제를 풀 수 있다.

 

괄호를 여는 행위를 할 때, 그 pair를 스택에 등록하고 문자가 들어올 때, 해당 문자가 여는 부분이라면 다시 pair를 등록

닫는 문자면 가장 최근 문자와 같은지(pair인지)확인하면 된다.

 

아.. 어려웠다..

 

 

 

 

---

구현코드

 

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        pair = {')': '(', ']': '[', '}': '{'}
        
        for char in s:
            if char in pair.values():  # 여는 괄호일 때
                stack.append(char)
            elif char in pair:  # 닫는 괄호일 때
                if not stack or stack[-1] != pair[char]:
                    return False
                stack.pop()
            else:
                return False  # 괄호 외 다른 문자가 들어오면 잘못된 입력

        return not stack  # 스택이 비어있으면 True, 남아있으면 False