📌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.

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 <= $10^4$
• s consists of parentheses only '()[]{}'.

leetcode 에서 풀기

---

📝Solution

✏️ Stack

class Solution:
    def isValid(self, s: str) -> bool:
        stack=[]
        brackets={'}':'{',')':'(',']':'['}
        for bracket in s:
            if bracket in brackets.values(): #Opening bracket 
                stack.append(bracket)
            else:# Closing bracket
                if stack and brackets[bracket]==stack[-1] :  
                    stack.pop()
                else: 
                    return False
        
        if stack:
            return False
        return True

• Time complexity : $O(N)$
• stack 에 opening bracket 을 담고 closing bracket 이 들어 올때 마다 1. stack이 비어있지 않고, 2. stack 의 top 에 알맞은 opening bracket 이 존재한다면 stack에서 꺼낸다.
• False
  1. 알맞은 bracket 이 존재하지 않는 경우 , ex) s='(]'
  2. 반복문 도중 빈 stack 인 경우, ex) s=']'
  3. 반복문을 다 돈 뒤에도 stack이 비워지지 않은 경우, ex) s='({}'
• True
  1. 반복문을 다 돈 뒤 stack 이 다 비워진 경우

https://medium.com/@shahad9381/checking-parentheses-balance-using-stack-ce939faca1c3