关于leetcode:每日一练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/probl…

办法一：栈+哈希表

思路剖析

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();
}