Skip to content

0020.有效的括号

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

有效字符串需满足：

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

示例 1：

输入：s = "()"

输出：true

示例 2：

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

输出：true

示例 3：

输入：s = "(]"

输出：false

示例 4：

输入：s = "([])"

输出：true

示例 5：

输入：s = "([)]"

输出：false

提示：

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

思路

举个例子理解执行流程,比如输入 s = "()[]{}":

1.遇到 '(' → 左括号，压入栈 → 栈：['(']

2.遇到 ')' → 右括号，查 bracketMap[')'] 是 '('。栈顶是 '('，匹配 → 弹出栈顶 → 栈：[]

3.遇到 '[' → 左括号，压入栈 → 栈：['[']

4.遇到 ']' → 右括号，查 bracketMap[']'] 是 '['。栈顶是 '['，匹配 → 弹出栈顶 → 栈：[]

5.遇到 '{' → 左括号，压入栈 → 栈：['{']

6.遇到 '}' → 右括号，查 bracketMap['}'] 是 '{'。栈顶是 '{'，匹配 → 弹出栈顶 → 栈：[]

7.遍历结束后，检查栈是否为空：

  • ✅ 栈为空 → 所有左括号都找到了对应的右括号，返回 true。
  • ❌ 栈不为空 → 还有左括号没被匹配，返回 false。

解答

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        unordered_map<char,char>bracketMap={
            {')','('},{'}','{'},{']','['}
        };

        for(char c:s){
            if(bracketMap.count(c)){
                if(stk.empty()||stk.top()!=bracketMap[c])   return false;
                stk.pop();
            }else stk.push(c);
        }
        return stk.empty();
    }
};