Leetcode 有效的括号

Leetcode 有效的括号
Tags:
Categories:

有效的括号

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

解题思路

将给定字符串打散成数组
初始化字典, 右侧括号为键, 左侧括号为值
循环数组中的每个字符

如果当前字符不是字典的键(即不是右侧括号), 将当前字符追加到一个空数组stack
否则(即当前字符是右侧括号),

判断stack不为空的情况下, 最后一个元素是否等于字典中当前字符键的值
相等则继续判断下一个字符
不相等即返回False,
最后判断stack, 非空返回False

Answer

 1#
 2# @lc app=leetcode.cn id=20 lang=python3
 3#
 4# [20] 有效的括号
 5#
 6
 7# @lc code=start
 8class Solution:
 9    def isValid(self, s: str) -> bool:
10        s = list(s)
11        dic = {")":"(","]":"[","}":"{"}
12        stack = []
13        for i in s:
14            if not i in dic:
15                stack.append(i)
16            else:
17                if stack and stack.pop() == dic[i]:
18                    pass
19                else:
20                    return False
21        return True if not stack else False
22# @lc code=end

Accepted

76/76 cases passed (36 ms)
Your runtime beats 90.49 % of python3 submissions
Your memory usage beats 5.22 % of python3 submissions (13.8 MB)