[파이썬][Leetcode][릿코드] Valid Parentheses

1. 문제

20. Valid Parentheses

Easy

---

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

 

Constraints:

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

출처: Leetcode, https://leetcode.com/

2. 해결방법 시간복잡도

1. 스택 O(N)

3. 문제 해결 및 코드

---

• 주석을 참고하면서 이해를 돕습니다.

4. 알고리즘 및 해설

1. 스택과 딕셔너리를 통해 문제를 해결하였다.
   • 괄호문제들은 보통은 대게 스택으로 간단하게 풀이가 가능하다.
2. 반복문을 통해 해당 값이 괄호를 여는 경우라면 스택에 넣는다.
   • 이때 괄호가 닫히는 문구가 열린 문구와 쌍을 이룬다면 스택에서 빼준다.
3. 최종적으로 스택안에 뭔가가 존재한다면(괄호가 열려있거나 하나 더 닫혀있거나) False를 반환하고 아니라면 True를 반환한다.