多味的LeetCode --- 20. 有效的括号

柔光的暖阳◎ 2022-11-11 13:03 156阅读 0赞

**题目描述：**

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

有效字符串需满足：

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

示例 1：

输入：s = "()"
    输出：true

示例 2：

输入：s = "()[]{}"
    输出：true

示例 3：

输入：s = "(]"
    输出：false

示例 4：

输入：s = "([)]"
    输出：false

示例 5：

输入：s = "{[]}"
    输出：true

提示：

1.  1 <= s.length <= 104
2.  s 仅由括号 ‘()\[\]\{\}’ 组成

--------------------

**解题思路1:**

通过示例，找出两个非常重要的规律：

1.  先出现的左括号，后匹配；
2.  借助栈，把左括号入栈中.

--------------------

**代码1：**

class Solution:
        def isValid(self, s: str) -> bool:
            length = len(s)
            if length % 2 == 1:
                return False
            
            pairs = {
        
                ")":"(",
                "}":"{",
                "]":"[",
            }
            stack = list()
            for ch in s:
                if ch in pairs:
                    if not stack or stack[-1] != pairs[ch]: # 如果栈中元素已经匹配完或无法正常匹配，返回False
                        return False 
                    stack.pop() # 左右括号正常匹配之后，把相应的左括号弹出
                else:
                    stack.append(ch) # 遇到还没有进栈的左括号，将其入栈
            return not stack

--------------------

**参考链接:**

[https://leetcode-cn.com/problems/valid-parentheses/solution/you-xiao-de-gua-hao-by-leetcode-solution/][https_leetcode-cn.com_problems_valid-parentheses_solution_you-xiao-de-gua-hao-by-leetcode-solution]

--------------------

**题目来源：**

[https://leetcode-cn.com/problems/valid-parentheses][https_leetcode-cn.com_problems_valid-parentheses]

[https_leetcode-cn.com_problems_valid-parentheses_solution_you-xiao-de-gua-hao-by-leetcode-solution]: https://leetcode-cn.com/problems/valid-parentheses/solution/you-xiao-de-gua-hao-by-leetcode-solution/
[https_leetcode-cn.com_problems_valid-parentheses]: https://leetcode-cn.com/problems/valid-parentheses