Leetcode 20 - Valid Parentheses

Catalogue

1. 1. Question
2. 2. Analysis
3. 3. Code

Question

Given a string 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.
   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

Analysis

相比于采用多个 if else 来判断括号，使用字典储存括号对应关系并用于判断更加简洁。如果当前字符为 '{([' 之一，则往一个额外列表中添加左括号，否则如果额外列表为空，或者当前括号和额外列表最后一个括号不对应，则不符合规则。

Code

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        dic = {'{': '}', '(': ')', '[': ']'}
        res = []
        for x in s:
            if x in dic:
                res.append(x)
            elif not res or x != dic[res.pop()]:
                return False
        return not res