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 提交结果
4 解题心得
- C++的STL中,栈stack在解题时非常好用。
- 哈希表在使用时,有空间复杂度。
- 哈希表的count()方法,可以在哈希表中查找元素。