HHot 100C++ 图解

20. 有效的括号

一句话套路左括号入栈,右括号配栈顶 + 结束判空

题目描述

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

有效字符串需满足:

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

 

示例 1:

输入:s = "()"

输出:true

示例 2:

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

输出:true

示例 3:

输入:s = "(]"

输出:false

示例 4:

输入:s = "([])"

输出:true

示例 5:

输入:s = "([)]"

输出:false

 

提示:

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

思路

时间O(n)
空间O(n)

思路

遇到左括号入栈;遇到右括号则栈顶必须是配对的左括号。

易错

① 右括号来时栈可能为空(")(" 这种情况)—— 必须判空再 top();

  • ② 结束时栈必须为空,否则 "((" 会被误判为合法。

图解

( 0 ) 1 [ 2 ] 3 { 4 } 5 ( ) [ ] { }
遍历字符:是左括号就入栈;是右括号就检查栈顶是否为对应左括号。栈是 LIFO,天然匹配「最近嵌套」的一对。

逐帧动画

1 / 4

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/12_stack.cpp21 行
namespace lc0020 {
class Solution {
 public:
  bool isValid(const string& s) {
    stack<char> st;
    for (char c : s) {
      if (c == '(' || c == '[' || c == '{') {
        st.push(c);
      } else {
        if (st.empty()) return false;  // 右括号多余
        char open = st.top();
        st.pop();
        if (c == ')' && open != '(') return false;
        if (c == ']' && open != '[') return false;
        if (c == '}' && open != '{') return false;
      }
    }
    return st.empty();  // 左括号不能剩余
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q20_valid_parentheses9 行
lc0020::Solution s;
CHECK_TRUE(s.isValid("()"));
CHECK_TRUE(s.isValid("()[]{}"));
CHECK_FALSE(s.isValid("(]"));
CHECK_FALSE(s.isValid("([)]"));  // 交叉嵌套非法
CHECK_TRUE(s.isValid("{[]}"));
CHECK_FALSE(s.isValid("]"));   // 以右括号开头
CHECK_FALSE(s.isValid("("));   // 结束时栈非空
CHECK_TRUE(s.isValid(""));

↑↓ 选择↵ 打开/ 随时唤起