20. Valid Parentheses.md

20. Valid Parentheses

思路

用一个栈来存放左括号，每次遇到左括号就将其入栈，遇到右括号就查看是否与栈顶元素配对，若能配对则pop栈顶元素，继续下一循环，否则返回false。 退出循环后，若栈不空，说明还剩下未配对的左括号，则应该返回false。
时间复杂度O(n), 空间复杂度O(n)

C++

class Solution {
private:
    bool isLegal(const char& a, const char&b){
        if(a == '(' && b == ')') return true;
        if(a == '[' && b == ']') return true;
        if(a == '{' && b == '}') return true;
        return false;
    }
public:
    bool isValid(string s) {
        stack<char>stk;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == ')' || s[i] == '}' || s[i] == ']'){
                if(stk.empty() || !isLegal(stk.top(), s[i])) return false;
                stk.pop();
            }
            else stk.push(s[i]);
        }
        if(!stk.empty()) return false;
        return true;
    }
};