Valid Parentheses – LeetCode 20
Problem
Description
Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.
The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.
Answer
Original
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
bool isValid(string s) {
int little = 0, square = 0, big = 0, end = s.size(), level = 2;
for(int i = 0; i != end; ++i){
if(s[i] == '(') {little += level++;}
if(s[i] == ')') little -= --level;
if(s[i] == '[') { square += level++;}
if(s[i] == ']') square -= --level;
if(s[i] == '{') { big += level++;}
if(s[i] == '}') big -= --level;
}
return !(little || square || big);
}
};
|
思路
要求验证字符串的括号是否闭合，使用三个int变量记录左右括号，同时使用level来记录括号的层级。例如([{}])，就可视作( 1 [ 2 { 3 } 2 ] 1 )。最后对三个int变量进行判断即可得到答案。因为需要完整遍历字符串，所以时间复杂度恒为$O(n)$，空间复杂度是$O(1)$。
耗时$3$ ms，排名$90.48\%$。
Better
思路
既然括号是临近匹配的，那么就可以使用FIFO的数据结构来进行管理，于是可以使用Stack。STL的Stack都会用，那么下面就用手动模拟的试试。相对与原方案，优势在于在发现括号不正确匹配时可以提前返回，节省一部分开销。时间复杂度依旧为$O(n)$，空间复杂度是$O(1)$。
耗时$3$ ms，排名$90.48\%$。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
bool isValid(string s) {
int top=-1,index=0,length=s.size();
char* stack=(char*)malloc(sizeof(char)*length);
while(index<length){
if(s[index]==')'){
if(top>=0 && stack[top]=='(')top--;
else return false;
}else if(s[index]=='}'){
if(top>=0 && stack[top]=='{')top--;
else return false;
}else if(s[index]==']'){
if(top>=0 && stack[top]=='[')top--;
else return false;
}else stack[++top]=s[index];
index++;
}
return top==-1;
}
};
|