每日一练（36）：有效的括号

---

title: 每日一练（36）：有效的括号

categories:[剑指offer]

tags:[每日一练]

date: 2022/03/15

---

每日一练（36）：有效的括号

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

示例 1：

输入：s = "()"

输出：true

示例 2：

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

输出：true

示例 3：

输入：s = "(]"

输出：false

示例 4：

输入：s = "([)]"

输出：false

示例 5：

输入：s = "{[]}"

输出：true

提示：

1 <= s.length <= 104

s 仅由括号 '()[]{}' 组成

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/valid-parentheses

方法一：栈+哈希表

思路分析

1. 有效括号字符串的长度，一定是偶数！
2. 右括号前面，必须是相对应的左括号，才能抵消！
3. 右括号前面，不是对应的左括号，那么该字符串，一定不是有效的括号！

bool isValid(string s) {
    if (s.size() % 2) {
        return false;
    }
    unordered_map<char, char> pairs = {
        {')', '('},
        {']', '['},
        {'}', '{'}
    };
    stack<char> stk;
    for (char ch : s) {
        if (pairs.count(ch)) {
            if (stk.empty() || stk.top() != pairs[ch]) {
                return false;
            }
            stk.pop();
        } else {
            stk.push(ch);
        }
    }
    return stk.empty();
}

方法二：栈

bool isValid(string s) {
    if (s.size() % 2) {
        return false;
    }
    stack<char> st;
    for (auto ss : s) {
        if (ss == '(') {
            st.push(')');
        } else if (ss == '[') {
            st.push(']');
        } else if (ss == '{') {
            st.push('}');
        } else {
            if (st.empty() || st.top() != ss) {
                return false;
            } else {
                st.pop();
            }
        }
    }
    return st.empty();
}