---
title: "#20 Valid Parentheses"
tags: LeetCode, Top100
---
#20 Valid Parentheses
==

題目描述
--
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: false

解題思維
--
就很典型的stack問題。

Stack
--

class Solution:
    def isValid(self, s: str) -> bool:
        right = {')': '(', ']': '[', '}': '{'}
        stack = ['']
        for str in s:
            if str in right:
                if stack[-1] == right[str]:
                    stack.pop()
                else:
                    return False
            else:
                stack.append(str)
        if len(stack) == 1:
            return True
        return False