20. Valid Parentheses

2,135次阅读

共计 635 个字符，预计需要花费 2 分钟才能阅读完成。

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.

Example 1:

Input: "()"
Output: true

Example 2:

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

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

解法

class Solution:
    def isValid(self, s: 'str') -> 'bool':
        
        dict_data={')':'(','}':'{',']':'['}
        left=set(['(','{','['])
        right=set([')','}',']'])
        tmp_list=[]
        for x in s:
            if x in left:
                tmp_list.append(x)
            else:
                tmp=dict_data[x]
                if len(tmp_list)<1 or tmp_list[-1]!=tmp:
                    return False
                tmp_list.pop()
        if tmp_list:
            return False
        
        return True

正文完

请博主喝杯咖啡吧！