LeetCode.20-----有效的括号

题目链接

首先如果字符串能构成有效的括号，一定是偶数个，奇数就可以排除了。我们先遍历字符串，遇到左括号暂存，若后面有右括号和最晚暂存的括号匹配，这和栈的先进后出一样了，那就可以借助栈来暂存左括号，遇到右括号看栈顶元素能否匹配。循环结束，若此时栈为空就返回true。

动图演示：

代码如下：

class Solution {
public:
    bool isValid(string s) {
        //奇数个数不能成功匹配括号
        int n = s.size();
        if(n % 2 == 1) return false;
        
        stack st;
        for(auto ch : s)
        {
            //左括号就入栈
            if(ch == '(' || ch == '[' || ch == '{') st.push(ch);
            //右括号的情况
            else
            {
                if(st.empty()) return false;//栈为空，说明栈里没有和括号匹配的
                char topChar = st.top();
                st.pop(); 
                //不匹配的情况，返回false
                if((ch == ')' && topChar != '(') ||
                   (ch == ']' && topChar != '[') ||
                   (ch == '}' && topChar != '{')) 
                return false;
            }
        }
        return st.empty();
    }
};

时间复杂度;O(n)
空间复杂度:O(n)