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:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Example 1

Input: s = "()"
Output: true

Example 2

Input: s = "()[]{}"
Output: true.

Example 3

Input: s = "(]"
Output: false

Example 4

Input: s = "([)]"
Output: false

Example 5

Input: s = "{[]}"
Output: true

Constraints:

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

내 풀이

class Solution:
  def isValid(self, s: str) -> bool:
    left = ["(", "{", "["]
    right = [")", "}", "]"]
    result = []
    if len(s) == 1 or s[0] in right:
      return False
    else:
      for i in s:
        if i in left:
          result.append(i)
        else:
          # "(){}}{" 같은 문자열 대비 
          if len(result) == 0:
            return False
          idx = right.index(i)
          if left[idx] == result[-1]:
            result.pop()
          else:
            result.append(i)
      if len(result) == 0:
          return True
      return False

Runtime: 32 ms, faster than 68.28% of Python3 online submissions for Valid Parentheses.
Memory Usage: 14.1 MB, less than 5.29% of Python3 online submissions for Valid Parentheses.

인풋 s와 비교하기 위해 왼쪽 괄호와 오른쪽 괄호를 나눠서 리스트를 만들어주고, s 문자열을 스택 자료구조로 쌓아줄 빈 리스트를 만든다.

만약 s가 괄호 하나로만 구성되어있거나, 오른쪽 괄호로 시작하면 False를 리턴해준다. True가 나올 수 없는 구조기 때문이다.

왼쪽 괄호는 무조건 스택에 넣고 오른쪽 괄호가 나왔을 때 스택의 가장 위 요소와 비교해 짝이 맞으면 스택에서 제거(pop)한다. 짝이 맞지 않으면 스택에 쌓는다. 스택에서 모든 괄호가 비워지면(=길이가 0이면) 괄호 짝이 맞는다는 이야기이므로 True를 리턴하고 그렇지 않으면 False를 리턴한다.

다른 사람 풀이

class Solution:
  def isValid(self, s):
    bracket_map = {"(": ")", "[": "]",  "{": "}"}
    open_par = set(["(", "[", "{"])
    stack = []
    for i in s:
      if i in open_par:
        stack.append(i)
      elif stack and i == bracket_map[stack[-1]]:
        stack.pop()
      else:
        return False
    return stack == []

Published 2 Sep 2020