写在前面
该专栏作为算法题笔记，记录算法的思路、遇到的问题，以及能跑的代码，持续更新中！
推荐一款面试、刷题神器牛客网：👉开始刷题学习👈
1.题目描述
描述
给出一个仅包含字符’(’,’)’,’{’,’}’,’[‘和’]’,的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，"()“和”()[]{}“都是合法的括号序列，但”(]“和”([)]"不合法。
数据范围：字符串长度 0 ≤ n ≤ 10000 0\le n \le 100000≤n≤10000
要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
2.算法设计思路
使用栈可以很方便地解决这个问题。下面是算法过程描述：
每次从字符串读取一个括号
与栈顶括号进行比较
若匹配，则将栈顶括号出栈
若不匹配，则将读取到的括号压入栈
直到字符串为空时，检查栈是否为空。
若栈空，则说明字符串是合法的括号序列；
若栈不为空，那么字符串是不合法的括号序列。
来张草图:
3.算法实现（C++）
#include<stack> class Solution { public: /** * @param s string字符串 * @return bool布尔型 */ bool match(char a, char b){ //判断ab是否为匹配的括号 if(a == '(' && b == ')'){ return true; }else if(a == '[' && b == ']'){ return true; }else if(a == '{' && b == '}'){ return true; } return false; } bool isValid(string s) { // write code here stack<char> sta; for(int i = 0; s[i] != '\0'; i++){ if(!sta.empty() && match(sta.top(), s[i])){ sta.pop(); }else{ sta.push(s[i]); } } if(sta.empty()){ return true; } return false; } };
4.运行结果
成功通过！
