Description
Given a string s
containing only three types of characters: '('
, ')'
and '*'
, return true
if s
is valid.
The following rules define a valid string:
- Any left parenthesis
'('
must have a corresponding right parenthesis')'
. - Any right parenthesis
')'
must have a corresponding left parenthesis'('
. - Left parenthesis
'('
must go before the corresponding right parenthesis')'
. '*'
could be treated as a single right parenthesis')'
or a single left parenthesis'('
or an empty string""
.
Example 1:
Input: s = "()" Output: true
Example 2:
Input: s = "(*)" Output: true
Example 3:
Input: s = "(*))" Output: true
Constraints:
1 <= s.length <= 100
s[i]
is'('
,')'
or'*'
.
Solution
Python3
class Solution:
def checkValidString(self, s: str) -> bool:
N = len(s)
cmin = cmax = 0
for x in s:
if x == "(":
cmin += 1
cmax += 1
elif x == ")":
cmin -= 1
cmax -= 1
else:
cmin -= 1
cmax += 1
if cmax < 0: return False
cmin = max(0, cmin)
return cmin == 0
Java
class Solution {
public boolean checkValidString(String s) {
int low = 0;
int high = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
low++;
high++;
} else if (s.charAt(i) == ')') {
if (low > 0) {
low--;
}
high--;
} else {
if (low > 0) {
low--;
}
high++;
}
if (high < 0) {
return false;
}
}
return low == 0;
}
}