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