代码随想录二刷 |队列与栈 |有效的括号
题目描述
给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1:
输入:s = “()”
输出:true
示例 2:
输入:s = “()[]{}”
输出:true
示例 3:
输入:s = “(]”
输出:false
提示:
- 1 <= s.length <= 104
- s 仅由括号 ‘()[]{}’ 组成
解题思路 & 代码实现
整体思路是遍历字符串,遇到左方向的括号时,将对应的右方向括号放入栈中,后面遇到对应的右方向的括号就将栈中的括号弹出。遍历完成后,如果栈为空,说明没有不匹配的情况,return true。
有三种不匹配的状态
- 字符串里左方向的括号多余了
( ( {
} )
- 字符串里右方向的括号多余了
( {
[ ] } ) )
- 括号没有多余,括号的类型没有匹配上
([{
]])
第一种:
遍历完成之后栈不为空,return false
第二种:
遍历过程中栈为空,说明右括号多余,return false
第三种:
遍历过程中发现没有要匹配的括号,return false
class Solution {
public:
bool isValid(string s) {
// 如果s的长度为奇数,一定不符合要求
if (s.size() % 2 != 0) return false;
stack<char> st;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '{') st.push('}');
else if (s[i] == '[') st.push(']');
else if (s[i] == '(') st.push(')');
// 第二、第三种情况
else if (st.empty() || s[i] != st.top()) return false;
else st.pop();
}
// 第一种情况
return st.empty();
}
};