LeetCode - 20. Valid Parentheses

[LeetCode] 20. Valid Parentheses

LeetCode 20번 문제를 풀어보았다.. Link

Problem

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.

Intuition

입력의 역순으로 판단(?)이 이루어져야하는 문제이다.

예시 케이스들은 순서대로만 나와있지만, 만약 ([])과 같은 케이스가 있을 경우, (보다 [이 더 먼저 판단(?)이 되어야 함

따라서 Stack 자료구조를 쓰는 것이 적절할 것으로 보인다.

Approach

아래의 접근방식을 생각해내면서 처음에 빼먹었던 부분은 바로 7번이다.

종류가 다를 경우 반복문안에서 False를 Return해버리기 때문에 반복문을 무사히 통과했다면 False case가 없을 거라고 생각하고 처음에는 그냥 True를 Return하도록 했었다.

하지만 이는 여는괄호 하나로 된 s가 입력일 경우 문제가 발생하기 때문에 현재의 7번과 같이 Stack이 비어있는지 아닌지를 판별해줘야만 한다.

1. 여는 괄호가 key, 닫는 괄호가 value인 dictionary를 만든다.
2. string의 character를 하나씩 본다.
3. 여는 괄호가 나오면 Stack에 넣는다.
4. 닫는 괄호일 경우 stack 최상단에 있는 것과 같은 종류일 경우 stack에서 pop한다.
5. 종류가 다르면 False를 return한다.
6. string을 전부 볼 때 까지 반복한다.
7. stack이 비어있으면 True, 없으면 False를 return한다.

Complexity

• Time complexity:

  주어진 문자열의 길이를 n이라고 할 때 \(O(n)\)

• Space complexity: 내 경우에는 Dictionary도 만들었기 때문에.. \(O(max(3, n))\)

My Code

class Solution:
    def isValid(self, s: str) -> bool:
        """
        만약 위의 case를 고려하지 않는다고 하면
        1. 여는 괄호가 key, 닫는 괄호가 value인 dictionary를 만든다.
        2. string의 character를 하나씩 본다.
        3. 여는 괄호가 나오면 Stack에 넣는다.
        4. 닫는 괄호일 경우 stack 최상단에 있는 것과 같은 종류일 경우 stack에서 pop한다.
        5. 종류가 다르면 False를 return한다.
        6. string을 전부 볼 때 까지 반복한다.
        7. stack이 비어있으면 True, 없으면 False를 return한다.
        """

        dict = {'(':')', '{':'}', "[":"]"}
        key_dict = dict.keys()
        value_dict = dict.values()
        stack = []
        for c in s:
            if c in key_dict:
                stack.append(c)
            else:
                if stack and dict[stack[-1]] == c:
                    stack.pop(-1)
                else:
                    return False
        if stack:
            return False
        else:
            return True