LeetCode20. Valid Parentheses

题目:

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:
        stack = []
        mapping = {")": "(", "}": "{", "]": "["}

        for chr in s:
            if chr in mapping:
                top_element = stack.pop() if stack else '#'

                if mapping[chr] != top_element:
                    return False

            else:
                stack.append(chr)
        return not stack

时空分析

时间复杂度 : 对每个元素需要执行push 或pop操作 ,为O(N)
空间复杂度:考虑最坏情况,所有元素都要push,那么是O(N)

Author Rewards

Leave a Reply

Your email address will not be published. Required fields are marked *