Leetcode第二十题(有效的括号)

题目描述:

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1： 输入：s = "()" 输出：true
示例 2： 输入：s = "()[]{}" 输出：true

示例 3： 输入：s = "(]" 输出：false
示例 4： 输入：s = "([)]" 输出：false
示例 5： 输入：s = "{[]}" 输出：true

无论是用数组栈，还是容器栈去解决括号匹配的问题，首先，遵循括号匹配的字符串任何一个前缀,其左括号的个数一定是大于等于右括号的个数的。其思路都是先用hash表存储所有类型的括号，左括号为key，右括号为value，遍历括号字符串，如果当前字符为左括号，那么入栈该左括号对应的右括；如果为右括号，将该右括号与栈顶字符比较, 如果不相等或者此时栈为空, 那么肯定括号不匹配，直接返回false。反之相等就出栈该右括号, 如果遍历完字符串后, 栈为空, 那么说明括号是左右相匹配的, 返回true。

数组栈:

class Solution {
public:
    bool isValid(string s) {
        unordered_map<char,char> pairs = {
            {'(',')'},{'{','}'},{'[',']'}
        };
        char stck[4096];
        int top = -1;
        for(int i = 0;i < s.length();i++){
            if(pairs.find(s[i]) != pairs.end()){  //当前为左括号,入栈右括号
                stck[++top] = pairs[s[i]];
            }else{
                if(top == -1 || stck[top] != s[i]) //当前为右括号不等于栈顶括号,或者栈空
                    return false;
                else                               //当前为右括号等于栈顶括号,出栈
                    stck[top--];
            }
        }
        return top == -1;                         //栈为空返回true
    }
};

容器栈:

class Solution {
public:
    bool isValid(string s) {
        unordered_map<char,char> pairs = {
            {'(',')'},{'{','}'},{'[',']'}
        };
        stack<char> st;
        for(int i = 0;i < s.length();i++){
            if(pairs.find(s[i]) != pairs.end()){  //当前为左括号,入栈右括号
                st.push(pairs[s[i]]);
            }else{
                if(st.empty() || st.top() != s[i]) //当前为右括号不等于栈顶括号,或者栈空
                    return false;
                else                               //当前为右括号等于栈顶括号,出栈
                    st.pop();
            }
        }
        return st.empty();                         //栈为空返回true
    }
};