LeetCode 有效的括号

有效的括号


题目来源:https://leetcode-cn.com/problems/valid-parentheses/

题目


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

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

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

示例 3:

输入: "(]"
输出: false

示例 4:

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

示例 5:

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

解题思路


  1. 思路:栈;
  2. 对括号进行映射,右括号为键,左括号为值;
  3. 如果遇到左括号,直接将其入栈。等待后面匹配处理;
  4. 如果遇到右括号,检查栈顶的元素。若是同类型则弹出继续处理接下的部分。否则,直接返回 False;
  5. 如果最终遍历完成后,栈中还有元素,同样返回 False。

代码实现


class Solution:
    def isValid(self, s: str) -> bool:
        '''判断是否是有效的括号

        Args:
            str: 包含括号的字符串
        
        Returns:
            返回判断的结果,满足条件:
                1. 左括号必须用相同的类型的右括号闭合。
                2. 左括号必须以正确的顺序闭合。
            空字符串可以被认为是有效的字符串
            返回类型为布尔型
        '''
        # 以栈形式存储左括号
        stack = []

        # 以右括号当成键映射对应类型的左括号
        prths_mapping = {'}': '{', ']': '[', ')': '('}

        # 遍历字符串,遇左括号则进行入栈
        for ch in s:
            # 对字符进行判断,是否为右括号
            if ch in prths_mapping:
                # 为右括号的情况下,判断 stack 栈顶是否是同类型的左括号
                # pop 出栈顶的字符
                # 若 stack 为空,用 '?' 进行标记
                pop_prth = stack.pop() if stack else '?'

                # 如果左右括号不成对,直接返回 False
                if prths_mapping[ch] != pop_prth:
                    return False
            else:  # 左括号入栈
                stack.append(ch)
        # stack 最终为空,则表示为有效
        return not stack

实现效果



以上就是本篇的主要内容


欢迎关注微信公众号《书集所录》

你可能感兴趣的