题解28 | 知否知否，应是栈空字走#有效括号序列#

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)。