20. 有效的括号
一句话套路左括号入栈,右括号配栈顶 + 结束判空
题目描述
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1:
输入:s = "()"
输出:true
示例 2:
输入:s = "()[]{}"
输出:true
示例 3:
输入:s = "(]"
输出:false
示例 4:
输入:s = "([])"
输出:true
示例 5:
输入:s = "([)]"
输出:false
提示:
1 <= s.length <= 104s仅由括号'()[]{}'组成
思路
时间
O(n)空间
O(n)思路
遇到左括号入栈;遇到右括号则栈顶必须是配对的左括号。
易错
① 右括号来时栈可能为空(")(" 这种情况)—— 必须判空再 top();
- ② 结束时栈必须为空,否则 "((" 会被误判为合法。
图解
遍历字符:是左括号就入栈;是右括号就检查栈顶是否为对应左括号。栈是 LIFO,天然匹配「最近嵌套」的一对。
逐帧动画
1 / 4
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
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(); // 左括号不能剩余
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
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(""));