Leetcode 20. 有效的括号

可以将反括号先存入map中，而后如果当前字符能在map中查到，说明是反括号，否则是正括号。

但是结合map的使用和将反括号作为map的key，并不容易第一时间想到。

class Solution {
public:
    bool isValid(string s) {
        int n = s.size();
        if(n % 2) {
            // 如果字符串的长度为奇数，直接可以返回false
            return false;
        }

        // 因为是通过反括号来查找栈中有无对应的正括号，因此key是反括号。
        unordered_map<char, char> pairs = {
            {')', '('}, 
            {']', '['}, 
            {'}', '{'}
        };

        stack<char> stk;
        for (char ch : s) {
　　　　　　　　// 这里用count来判断是否map中存入当前字符串（是否是反括号），相比于用迭代器去接收并判断，大大简化了代码量
            if(pairs.count(ch))  // 如果对于某一个s中的元素，是反括号
            {
                if (stk.empty() || stk.top() != pairs[ch]) {
                    // 如果栈中没有与ch对应的正括号，或者栈已经为空
                    return false;
                }
                stk.pop(); // 将对应的正括号pop
            }
            else {
                stk.push(ch);
            }
        }
        return stk.empty();

    }
};

下面是最实用的代码。在栈里存储正括号，而后针对每个输入的反括号，逐一判断对应的栈顶和栈大小。

在判断匹配的正反括号时，也可以结合正反括号的ascii码判断，大大简化代码量。

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;

        for (auto c : s) {
            if (c == '(' || c == '[' || c = '{') stk.push(c);
            else {
                // (和)的ascii码相差1， [和]的ascii码相差2，{和}的ascii码相差2
                if(stk.size() && abs(stk.top() - c) <= 2) stk.pop();
                else return false;
            }
        }
        // 如果此时stk还不为空，说明有正括号没有与反括号匹配，不是合法的括号序列
        // 如果为空，说明是合法的括号序列
        return stk.empty();
    }
};