栈
解题思路
如果是左括号，则直接入栈；
如果是右括号，则将其与栈顶元素进行匹配；
- 如果匹配，则出栈；
- 如果不匹配，直接返回 false；
- 如果此时栈为空，则说明右括号多，直接返回 false；
最后检查栈是否为空，若不为空，说明左括号多，直接返回 false；
复杂度
-
时间复杂度
O(N)：正确的括号组合需要遍历 1 遍； -
空间复杂度
O(N)：哈希表和栈使用线性的空间大小；
代码实现
var isValid = function (s) {
let stack = [];
let obj = {
'(': ')',
'[': ']',
'{': '}'
};
for (let i = 0; i < s.length; i++) {
const ele = s[i];
if (ele in obj) {
// 正括号的场景：入栈
stack.push(ele);
} else {
if (stack.length === 0) return false;
// 反括号的场景：出栈
let top = stack.pop();
if (ele != obj[top]) return false; //不匹配
}
}
// 括号遍历结束，栈中还有数据则说明正括号过多，错误
return stack.length === 0;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 222. 完全二叉树的节点个数
上一篇
评论
