20. 有效的括号

题目：

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

有效字符串需满足：

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

提示：

• 1 <= s.length <= 104
• s 仅由括号 '()[]{}' 组成

示例 1：
输入：s = "()"
输出：true

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

示例 3：
输入：s = "(]"
输出：false

示例 4：
输入：s = "([)]"
输出：false

示例 5：
输入：s = "{[]}"
输出：true

自行解答：

思路分析：

一看到这道题，一般就能想到数据结构中的栈了，使用栈的特性即可完成分析。

1：初始化三个变量，栈charStack用于存储字符串中的每一个字符，stackTop代表栈顶元素

2：洗掉无效字符，包括字符长度为单数的，字符长度为0的，以右括号打头的字符串

3：开始循环

3.1：字符为左括号就入栈

3.2：字符为右括号就检查栈顶是不是和当前字符是不是一个配对

4：循环结束之后，检查栈中有无剩余元素，如果有则说明全部匹配

代码如下：

bool isValid(string s) {
    stack<char> charStack;
    bool result = false;
    char stackTop = NULL;
    if(s.length() % 2 != 0){
        return result;
    }
    if(s.length() == 0 || s[0] == ')'|| s[0] == '}'|| s[0] == ']'){
        return result;
    }
    for (int i = 0; i < s.length(); ++i) {
        if(s[i] == '(' || s[i]=='{' || s[i] == '['){
            charStack.push(s[i]);
            continue;
        }
      //到此不是左括号，并且栈中无数据了，说明存在多的右括号，
      // 测试case "(){}}{"
      //另外需要校验栈中有元素才能取栈顶，栈中没有元素是无法取栈顶的
        if(charStack.size() == 0){
            return result;
        }
        stackTop = charStack.top();
        if((s[i] == ')' && stackTop == '(') ||
            (s[i] == '}'&& stackTop == '{') ||
            (s[i] == ']' && stackTop == '[')) {
            charStack.pop();
        } else{
            return result;
        }
    }
    //运行到此处，栈中若还存在数据就说明不配对
    //测试case “((”
    if(charStack.size() == 0){
        result = true;
    }
    return result;
}

int main() {
    string s = "()";
    bool result = isValid(s);
    cout <<"result:" <<result<<endl;
    return 0;
}

复杂度分析：

时间复杂度：O（N），N为字符的长度，因为遍历了一次字符长度

空间复杂度：O（N），N为字符的长度，此处就说极端场景下会纯在此种空间复杂度，但是平均的时间复杂度不应这么大，因为字符有入栈和出栈，极端场景case：

“((((((”,字符会全部入栈

官方解答：

官方解答和上面的解答思路一样，实现略不相同，具体参考代码如下：

  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();
    }