[LEETCODE] 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:

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

 

Constraints:

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

 

 

내 풀이

class Solution:
    def isValid(self, s: str) -> bool:
        left_stack = []
        right_stack = []
        strs = [')', '}', ']']
        str_dict = {
            '(' : ')',
            '{' : '}',
            '[' : ']'
        }
        
        for idx, char in enumerate(s):
            if idx == 0 and char in strs:
                return False
            else:
                if char in strs:
                    right_stack.append(char)
                else:
                    left_stack.append(char)
        if right_stack == list(map(lambda x: str_dict[x], left_stack)):
            return True
        else:
            return False

 

이렇게 했는데 테스트 케이스는 성공했으나 제출하니 틀렸다함. 문제 이해를 잘못한듯. 아 이거 백준에서 전에 봤던거 같은데...
다른 곳에서 약간의 힌트를 찾아서 풀어서 제출했더니 성공....
짝을 맞춰서 소멸시키면서 푸는 문제였음

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        result = True
        str_dict = {
            '(' : ')',
            '{' : '}',
            '[' : ']'
        }
        r_str_dict= dict(map(reversed,str_dict.items()))
        
        for idx, char in enumerate(s):
            if idx == 0 and char in str_dict.values():
                return False
            else:
                if char in str_dict.keys():
                    stack.append(char)
                elif len(stack) != 0:
                    if (char in str_dict.values() and stack[-1] == r_str_dict[char]):
                        stack.pop()
                    else:
                        result = False
                        break
                else:
                    result = False
                    break
        if (len(stack) != 0):
            result = False
        return result

 

 

다른 풀이

class Solution:
    # @return a boolean
    def isValid(self, s):
        stack = []
        dict = {"]":"[", "}":"{", ")":"("}
        for char in s:
            if char in dict.values():
                stack.append(char)
            elif char in dict.keys():
                if stack == [] or dict[char] != stack.pop():
                    return False
            else:
                return False
        return stack == []

 

아나 나빼고 다 심플하게 짜나봐.
그런데 사고의 흐름은 비슷했따. 애초에 바깥 괄호를 key로 뒀으면 dict를 뒤집는 짓은 안했을듯...