Leetcode(20): Valid Parentheses

Leetcode(20): Valid Parentheses

2021, Aug 04    


問題說明

這一題是給定一個只含有『(){}[]』等六種字元的string，要求我們判斷該string是否符合數學上的格式。 也就是說，每一個左括號必須有配套的右括號存在，且順序必須要正確。 舉例而言，

  • –> 這是對的
  • [()] –> 這是對的
  • ]}{[ –> 這是錯的

思考方向

用一個stack就可以解決這個問題，關鍵在於我們必須maintein一個左括號跟右括號的對應關係， 也就是你必須要讓程式知道[]是一對的，{}則是另外一對。

code

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) <= 1:
            return False
        
        type_dict = {"(": ")", "{": "}", "[": "]"}
        reverse = {")": "(", "}": "{", "]": "["}
        con = []
        
        for c in s:
            if c in type_dict:
                con.append(c)
            elif con and con[-1] == reverse[c]:
                con.pop()   
            else:
                return False
        
        return not con

Photo by Joni Rajala on Unsplash

# leetcode