LeetCode 20.有效的括号
0. 题目描述
1.解题分析
括号匹配是一个挺经典的问题，因为之前学习数据结构的时候已经学习到这个巧妙的解法了——栈。思路如下：
实现代码如下：
#include<stack>
class Solution {
public:
bool isValid(string s) {
stack<char> judge;
for (int i = 0; i < s.length(); i++) {
if (!judge.empty()) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
judge.push(s[i]);
}
else if (s[i] == ')') {
if (judge.top() == '(') {
judge.pop();
}
else
return false;
}
else if (s[i] == ']') {
if (judge.top() == '[') {
judge.pop();
}
else
return false;
}
else if (s[i] == '}') {
if (judge.top() == '{') {
judge.pop();
}
else
return false;
}
}
else {
judge.push(s[i]);
}
}
return judge.empty();
}
};第一遍通过的时候用时36ms，觉得肯定是哪里的逻辑不够简化 。看了范例后才发现，在每次右括号得不到匹配的时候就可以判断这串括号是不能匹配的，直接return false就好了，不用再继续之后的检测。
附上优化前的部分代码：
else if (s[i] == ')') {
if (judge.top() == '(') {
judge.pop();
}
else {
judge.push(s[i]);
}
}
else if (s[i] == ']') {
if (judge.top() == '[') {
judge.pop();
}
else {
judge.push(s[i]);
}
}
else if (s[i] == '}') {
if (judge.top() == '{') {
judge.pop();
}
else {
judge.push(s[i]);
}
}复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(n)。