20。有效括号（LeetCode）

Question

我在面试时遇到了这个问题，你们究竟如何解决这个问题？

https://leetcode.com/problems/valid-parentheses/

20。有效括号

给定一个仅包含字符

'('

、

')'

、

'{'

、

'}'

、

'['

和

']'

的字符串 s，确定输入字符串是否有效。

输入字符串在以下情况下有效：

• 左括号必须用相同类型的括号封闭。

• 左括号必须按正确的顺序闭合。

• 每个右括号都有一个对应的相同类型的左括号。

示例1：

Input: s = "()"  
Output: true

示例2：

Input: s = "()\[\]{}"
Output: true

示例3：

Input: s = "(\]"
Output: false  

示例4：

Input: s = "(\[\])"
Output: true

我尝试过使用堆，但面试时没有成功。

Answer 1

您可以使用堆来检查队列中预期的右括号，复杂度为

O(n)

：

class Solution:
    def isValid(self, s: str) -> bool:

        if s[0] in ')]}':
            return False

        expected = {
            ')': '(',
            ']': '[',
            '}': '{',
        }

        open_list = []

        for char in s:
            if char in '([{':
                open_list.append(char)
            else:
                if len(open_list) == 0:
                    return False
                if open_list[-1] == expected[char]:
                    open_list.pop()
                else:
                    return False

        return len(open_list) == 0