題目:

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

An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

給定一個有大中小括號的字串,檢查它們是否兩兩相對

這題是明顯的stack題型,而我所實作的程式碼如下

class Solution:
    def isValid(self, s: str) -> bool:
        d={"(":0,")":"(","[":0,"]":"[","{":0,"}":"{"} #dictionary紀錄對應值
        l=[]
        for i in range(len(s)):
            if len(l)==0:
                l.append(s[i])
            else:
                if d[s[i]]==l[-1]:
                    l.pop()
                else:
                    l.append(s[i])
        return l==[]

讓字串堆疊入一個list,堆疊過程中一面確認字串尾端是否為欲堆入值的對應值,如果是就一同取出
以"{ { ( { } ) } }"為例,執行過程 list 變動如下:
{ --> {{ -->{{( --> {{({ --> {{({} --> {{( --> {{() --> {{ --> {{} --> { --> {} --> None
由此可知,如果最後 list 空無一物的話就表示括號們兩兩相對,反之則否
注意:如 list 無物, l[-1] 不存在,因此需多加個條件判斷式在無值時 append

最後執行時間30ms(faster than 94.29%)

那我們下題見