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