题解28 | 知否知否，应是栈空字走#有效括号序列#
有效括号序列
https://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2
class Solution {
public:
bool isValid(string s) {
// write code here
stack<char> str;
//期有佳人配才智 待到花开烂漫时
for( int i = 0; i < s.length(); i++){
if(s[i] == '('){
str.push(')');
}
else if(s[i] == '['){
str.push(']');
}
else if(s[i] == '{') {
str.push('}');
}//这个得先判空，防止上来就是个右括号
else if(str.empty()){
return false;
}//知否知否，应是栈空字走。
else if(str.top() == s[i]){
str.pop();
}
}
return str.empty();
}
};
基本思想：
该算法使用栈来判断输入的字符串是否有效。
遍历输入的字符串，如果遇到左括号，则将对应的右括号入栈；
如果遇到右括号，则判断栈顶元素是否与当前右括号相同，
如果相同则出栈，否则返回false。
最后判断栈是否为空，如果为空则表示输入的字符串有效，否则表示字符串无效。
时间复杂度：
遍历输入字符串需要O(n)的时间，其中n为字符串的长度。
空间复杂度：
使用了一个栈来存储括号，最坏情况下需要存储n/2个左括号，因此空间复杂度为O(n)。
2024考研数据结构 文章被收录于专栏
本人考研刷算法题，立此专栏练习强化。
