LeetCode 06: Valid Parentheses

문제링크: https://leetcode.com/problems/valid-parentheses/

Problem

괄호들이 이어진 string(e.g., "([{]})" 에서 괄호들이 주어진 조건에 맞게 이어져있는지 확인하는 문제이다

1. 열린 괄호는 같은 type의 닫힌 괄호로 닫혀야 한다.
2. 열린 괄호는 순서에 따라 닫혀야한다.
3. 모든 닫힌 괄호는 해당하는 같은 type의 열린 괄호가 주어져 있어야 한다.

Solution

Stack의 자료구조를 활용하여 문제를 해결하면 쉽게 해결 가능하다.

주어진 string을 차례로 순회하면서,

1. 열린 괄호가 보일 시 해당하는 닫힌 괄호를 stack에 push해주고,

2. 닫힌 괄호가 보일시에는 stack에서 pop한 괄호와 해당 닫힌 괄호가 동일한지 확인 후,
   동일하지 않으면 False를 return해주면 된다.

최종적으로 stack이 비어있을 시에 모든 열린 괄호들이 해당하는 닫힌 괄호와 매칭이 완료된 것이므로 return True를 해주면 된다.

stack = []
for idx in range(len(s)):
    if s[idx] == '(':
        stack.append(')')
    elif s[idx] == '{':
        stack.append('}')
    elif s[idx] == '[':
        stack.append(']')
    elif (len(stack)==0 or s[idx] != stack.pop()):
        return False

return stack == []