[Leetcode] 20. Valid Parentheses

題目 : 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.
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="["