首页 > itarticle > leetcode練習解題

leetcode練習解題

admin 11月 14, 2020 0

Given a string 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.
Note that an empty string is also considered valid.

解題

以下方法用stack來記錄開括號。當我們遇到開括號時，我們把它存到stack中。如果我們遇到閉括號的話，我們就把stack最上的東西pop出來，判斷一下是否對應的括號。

代碼

class (object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        match = {'(':')','[':']','{':'}'}
        
        for c in s:
            if c in match:
                stack.append(c)
            else:
                if not stack or match[stack.pop()] != c:
                    return False
                
        return not stack