Valid Parentheses (in Python)

Problem

Given a string 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.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

Solution

스택을 이용해서 쉽게 풀 수 있는 기초 문제.

•string의 길이가 0이면 True.

•string의 길이가 1이면 False.

•string의 길이만큼 반복.

1. 스택의 가장 위에 있는 글자와 현재 글자를 합친 것이 dictionary 에 있다면 

- 스택의 가장 위에 있는 노드를 제거.

2. 그렇지 않다면

- 스택에 현재 글자 추가

•스택에 글자가 하나라도 남아 있을 경우 False 반환 그렇지 않다면 True 반환.

class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
 
        dic = [
            "()",
            "{}",
            "[]"
        ]
 
        n = len(s)
 
        if n < 1 :
            return True
        elif n == 1 :
            return False
 
        stack = []
 
        for i in s :
            if len(stack) > 0 and stack[-1]+i in dic :
                stack.pop()
            else :
                stack.append(i)
 
        if len(stack) > 0 :
            return False
 
        return True
            

Source

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