LeetCode69 - 有效的括号

📝 题目描述

题目链接：有效的括号

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

有效字符串需满足：

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

示例：

示例 1：

输入：s = "()"

输出：true

示例 2：

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

输出：true

示例 3：

输入：s = "(]"

输出：false

示例 4：

输入：s = "([])"

输出：true

示例 5：

输入：s = "([)]"

输出：false

提示：

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

💡 解题思路

方法一：栈

思路很简单，遇见左括号，直接入栈；遇见右括号：

1. 判断栈是否为空，为空则说明上来就是右括号，直接返回 false。
2. 不为空则判断栈顶是否为对应的左括号，是则出栈，不是则说明不符合匹配规则，返回 false。

最后判断栈是否为空，是则说明匹配完成，返回 true，否则说明还有未匹配的括号，返回 false。

🔧 代码实现

1、栈

class Solution {
public:
    bool isValid(string s) {
        // 奇数直接返回 false
        int n = s.size();
        if (n % 2 == 1) {
            return false;
        }
        stack<char> brackets;
        for (const auto c : s) {
            if (c == '{' || c == '[' || c == '(') {
                brackets.push(c);
            } else {
                if (brackets.empty()) return false;
                char t = brackets.top();
                if ((t == '{' && c != '}') || (t == '[' && c != ']') || (t == '(' && c != ')')) {
                    return false;
                } else {
                    brackets.pop();
                }
            }
        }
        return brackets.empty();
    }
};

📊 复杂度分析

1、栈

• 时间复杂度：$O(n)$，其中 n 是字符串 s 的长度。
• 空间复杂度：$O(n)$，栈中的字符数量为 $O(n)$。

🎯 总结

• 核心思想：注意括号要合法，不能交叉闭合。