[Leetcode] 20. Valid Parentheses

Problem Link: https://leetcode.com/problems/valid-parentheses/

Valid Parentheses - LeetCode

 

 

Solution 1. Stack

Python의 list에서 append 및 pop 연산은 O(1)이므로, 따로 stack을 구현하지 않았다.

 

Time: $O(N)$

Space: $O(N)$ 

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        str_len = len(s)
        
        seen = dict()
        LEFT = ['(', '[', '{']
        RIGHT = [')', ']', '}']
        PAIR = {'(': ')', '[': ']', '{': '}'}

        stack = []
        for par in s:
            if par in LEFT:
                stack.append(par)
            else:
                if len(stack) == 0:
                    return False
                
                left = stack.pop()
                pair = PAIR[left]

                if pair == par:
                    continue
                else:
                    return False

        if len(stack) > 0:
            return False
        else:
            return True

 

장황한 코드를 지우고 Discussion의 코드를 토대로 작성하였더니 32ms에서 11ms 정도로 실행시간이 감소했다.

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        str_len = len(s)
        
        seen = dict()
        LEFT = ['(', '[', '{']
        RIGHT = [')', ']', '}']
        PAIR = {'(': ')', '[': ']', '{': '}'}

        stack = []
        for par in s:
            if par in LEFT:
                stack.append(par)
            elif len(stack) == 0 or PAIR[stack.pop()] != par:
                return False

        return len(stack) == 0