Leetcode 678. Valid Parenthesis String

https://leetcode.com/problems/valid-parenthesis-string/

题意:括号匹配,增加了星号可以作为左括号、右括号或者星号

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
bool checkValidString(string s) {
if(s.size() == 0){
return true;
}

int left = 0, right = 0;
for(int i = 0; i < s.size(); i++){
if(s[i] == '(' || s[i] == '*')
left++;
else
left--;
if(left < 0)
return false;
}

if(left == 0)
return true;

for(int i = s.size() - 1; i >= 0; i--){
if(s[i] == ')' || s[i] == '*')
right++;
else
right--;
if(right < 0)
return false;
}

return true;
}
};

下面这个代码真的好难理解,一个人刷题太难了,心累。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
bool checkValidString(string s) {
if(s.size() == 0){
return true;
}

int left = 0, right = 0;
for(int i = 0; i < s.size(); i++){
if(s[i] == '('){
left++;
right++;
}
else if(s[i] == ')'){
if(left > 0)
left--;
right--;
}
else{
if(left > 0)
left--;
right++;
}
if(right < 0)
return false;
}

return left == 0;
}
};

0%