20. 有效的括号 – Blog of Aspirer

题目链接：https://leetcode.cn/problems/valid-parentheses/submissions/

这道题也没做出来，因为没有想到用栈来保存括号的对应关系，而是想着用递归判断子串是否是左右匹配的括号。看了官方题解才想明白，汗！！！

class Solution {
public:
    bool isValid(string s) {
        if (s.length() % 2 == 1) {
            return false;
        }

        unordered_map<char, char> mp = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };

        stack<char> st;
        for (int i = 0; i < s.length(); i++) {
            char c = s[i];
            if (mp.count(c)) {   // 'c' is a close bracket character
                if (st.empty() || st.top() != mp[c]) {  // if stack top can not match the new character, means can not close the bracket
                    return false;
                } else {    // close the bracket, pop it
                    st.pop();
                }
            } else {    // 'c' is a new open bracket character, push it
                st.push(c);
            }
        }

        return st.empty();
    }
};

class Solution {

public:

bool isValid(string s) {

if (s.length() % 2 == 1) {

return false;

}

unordered_map<char, char> mp = {

{')', '('},

{']', '['},

{'}', '{'}

};

stack<char> st;

for (int i = 0; i < s.length(); i++) {

char c = s[i];

if (mp.count(c)) { // 'c' is a close bracket character

if (st.empty() || st.top() != mp[c]) { // if stack top can not match the new character, means can not close the bracket

return false;

} else { // close the bracket, pop it

st.pop();

}

} else { // 'c' is a new open bracket character, push it

st.push(c);

}

return st.empty();

}

};