20.有效的括号：栈匹配

【LetMeFly】20.有效的括号：栈匹配

力扣题目链接：https://leetcode.cn/problems/valid-parentheses/

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

 

示例 1：

输入：s = "()"

输出：true

示例 2：

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

输出：true

示例 3：

输入：s = "(]"

输出：false

示例 4：

输入：s = "([])"

输出：true

示例 5：

输入：s = "([)]"

输出：false

 

提示：

• 1 <= s.length <= 104
• s 仅由括号 '()[]{}' 组成

解题方法：栈

遍历字符串，遇到左括号则入栈，遇到右括号则看栈顶元素与之是否匹配（匹配则出栈不匹配直接返回False），若遍历完栈为空才返回True。

• 时间复杂度$O(len(s))$
• 空间复杂度$O(len(s))$

也可以给栈中插入一个非括号哨兵字符来避免判断栈中是否有元素。

AC代码

C++

/*
 * @LastEditTime: 2026-10-01 09:22:00
 */
class Solution {
public:
    bool isValid(const string& s) {
        stack<char> st;
        for (char c : s) {
            if (c == '(' || c == '[' || c == '{') {
                st.push(c);
            } else if (st.empty()) {
                return false;
            } else {
                char a = st.top();
                st.pop();
                if (!(a == '(' && c == ')' || a == '[' && c == ']' || a == '{' && c == '}')) {
                    return false;
                }
            }
        }
        return st.empty();
    }
};

Python

class Solution:
    def isValid(self, s: str) -> bool:
        st = ['']
        pair = {
            '{': '}',
            '(': ')',
            '[': ']'
        }
        for c in s:
            if c in pair: st.append(c)
            elif pair.get(st.pop(), '') != c: return False
        return len(st) == 1

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源