[LeetCode] 20. Valid Parentheses (Python)

• Reference
• 카카오 기출 문제도 그렇고 이런 문제들은 싹다 stack을 사용해야 풀리는 문제
• and 연산은 굳이 조건 모두를 비교하지 않음
  • False가 나오면 즉시 비교를 중단함

Solution

import collections


class Solution:
    def isValid(self, s: str) -> bool:
        # parentheses_map = collections.defaultdict(str)
        # parentheses_map['('] = ')'
        # parentheses_map['{'] = '}'
        # parentheses_map['['] = ']'

        # i = 0
        # while i < len(s) - 1:
        #     if parentheses_map[s[i]] == s[i + 1]:
        #         i += 2
        #         continue
        #
        #     return False
        #
        # return True
        # 위처럼하면 "{[]}"와 같은 케이스에서 걸러짐 -> 즉 스택 써야 하는 문제

        parentheses_map = collections.defaultdict(str)
        parentheses_map[')'] = '('
        parentheses_map['}'] = '{'
        parentheses_map[']'] = '['

        stack = []
        for each in s:
            if stack and parentheses_map[each] == stack[-1]:
                    stack.pop()
                    continue

            stack.append(each)

        if stack:
            return False

        return True