[Leetcode] 20. Valid Parentheses

題目 : 20. Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

1. Michelle小梦想家參考解答

lookup : 建立(){}[]符號的字典

stack : 將讀進來的左括號暫存在這邊，用堆疊的方式存取

item : 目前讀到s的字元

line 8 : 如果讀取到的字元是lookup中的Key

line 9 : 用append()將item堆疊至stack容器中

line 10 : 如果這時候的stack沒有任何字元，代表沒有可以對應的左括號 -> False

用pop()方法將stack的最後一個字元讀取出來，並移除列表中的最後一個元素

如果最後一個元素在lookup中所對應的右括號和item不相同 -> False

line 12 : 如果直接回傳True可能會判斷錯誤，ex : s="["

所以要在最後return的時候判斷stack是否是清空的狀態

class Solution:
    def isValid(self, s: str) -> bool:
        
        lookup = {"(":")","{":"}","[":"]"}
        stack = []

        for item in s:
            if item in lookup:  # ({[
                stack.append(item)
            elif len(stack)==0 or lookup[stack.pop()] != item: # )}]
                return False
        return len(stack)==0  # s="["