valid-parentheses

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