---
# System prepended metadata

title: 20.Valid Parentheses
tags: [LeetCode]

---

###### tags: `LeetCode`
20.Valid Parentheses
===
主要是利用stack的方式來做，希望可以透過一進一出的方法確定所有的括號都是成雙成對的。

解法:
先弄一個dictionary，讓這些配對可以索引，然後做一個空的stack讓人可以塞東西進去跟吐出來。

走一個迴圈讓stack讀東西，讀的進去在字典裏面就往裡面塞，然後遇到反向的就回去檢查stack裡面是否之前有這東西，若沒有直接回傳false。

若前面一次次都確認無誤，還是得回去確認stack是否是空的因為可能有只有左邊的，所以再次確認stack為空可以變成true。
```
class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        lookup = { '(':')', '{':'}', '[':']' }
        for parenthese in s:
            if parenthese in lookup:
                stack.append(parenthese)
            elif len(stack)==0 or lookup[stack.pop()]!=parenthese:
                return False
        return len(stack)==0

```