力扣20、有效的括号（简单）

1 题目描述

图1 题目描述

2 题目解读

        给定的字符串只包含括号，判断这个字符串中的括号是否按照正确顺序出现，即这个字符串是否有效。

3 解法一：栈

        C++的STL中的stack，在解题时非常好用。

3.1 解题思路

        使用栈stk，并枚举字符串s的每一个字符。如果字符c是右括号，就进行以下判断，否则将其压入stk栈中：如果栈stk非空，且栈顶字符是对应的左括号，则弹出stk栈顶元素，否则返回false。

3.2 设计代码

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

3.3 复杂度分析

• 时间复杂度：。其中，n是字符串s的长度。
• 空间复杂度：。其中，表示字符集，本题中字符串只包含6种括号，=6。代码中使用了栈和哈希表，空间复杂度分别为和，将这两个空间复杂度相加，则得到总空间复杂度。

3.4 提交结果

图2 提交结果

4 解题心得

• C++的STL中，栈stack在解题时非常好用。
• 哈希表在使用时，有空间复杂度。
• 哈希表的count()方法，可以在哈希表中查找元素。