Leetcode.20 有效的括号

  关键词：vector, push_back(), pop_back(),  stack, push(), pop(), top()

1.题目

2.解答思路及解答

解答思路：

        左括号需要一个相同的括号，如果是括号嵌套的方式，可以类比“回文数”那题，利用双下标或者双指针遍历。

        但是实际上，会出现括号并列的方式，比如（）{} []这样。所以需要遍历整个字符串，在左括号右边寻找相应的），然而这个过程还可能出现（{}）（）这样的并不对称的有效括号形式，因此需要考虑合适的遍历方法。

        这里考虑到的是一种，类似计算器运算的“入栈、出栈”方法。比如在案例（{}）{}中，从左到右遍历，将遍历的左括号都放入一个vector，当vector最后一个元素，遇到对应的右括号时，就出vector，当vector最后为空时，即说明所有括号都可以按顺序匹配，否则则不能按顺序匹配。

        需要注意的几点是：

        遍历时，如果检测到左括号时，立即对下一位进行匹配，可能出现 下标超限、循环错误的问题。因此最明晰和直白的方法就是：

        遍历时，左括号丢入vector，不做操作。右括号出现时和*vector.end()进行匹配，移除vector最后一个数，这里需要注意，需要时刻注意vector是否为空，能否被移除。

class Solution {
public:
    bool isValid(string s) {
        vector<char> vecChar;
        int iSize = s.size();
        for(int i = 0; i < iSize; ++i)
        {
            if(s[i] == '('||
            s[i] == '{'||
            s[i] == '[')
            {
                vecChar.push_back(s[i]);
            }

            else
            {
                if(vecChar.empty())
                {
                    return false;
                }
                if((*(vecChar.end()-1) == '(' && s[i] == ')')
                ||(*(vecChar.end()-1) == '{' && s[i] == '}')
                ||(*(vecChar.end()-1) == '[' && s[i] == ']')
                )
                {
                    vecChar.pop_back();
                }
                else
                {
                    return false;
                }
            }
        }
        if(vecChar.empty())
        {
            return true;
        }
        else
        {
            return false;

        }

    }
};

3.优秀答案

答案1：map+stack

        该答案中利用map解决了常规思路中需要逐个if判断括号和对应特殊情况的问题。

        并且使用了一种特殊数据结构stack，并且引出了stack的部分函数top（），pop（）和push（）等。

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

        unordered_map<char, char> pairs = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };
        stack<char> stk;
        for (char ch: s) {
            if (pairs.count(ch)) {
                if (stk.empty() || stk.top() != pairs[ch]) {
                    return false;
                }
                stk.pop();
            }
            else {
                stk.push(ch);
            }
        }
        return stk.empty();
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/valid-parentheses/solutions/373578/you-xiao-de-gua-hao-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

4.技术总结