原题链接在这里:https://leetcode.com/problems/valid-parenthesis-string/description/
题目:
Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:
- 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. - An empty string is also valid.
Example 1:
Input: "()"
Output: True
Example 2:
Input: "(*)"
Output: True
Example 3:
Input: "(*))"
Output: True
Note:
- The string size will be in the range [1, 100].
题解:
Accumlate count of parenthesis and star.
When encountering *, increment starCount.
When encountering (, first make sure there is no more starCount than parCount.
If yes, these many more * could affect final decision. like ***(((. Finally, starCount >= parCount, but should return false.
Make starCount = parCount. Then increment parCount.
When encountering ), before decrementing parCount, if both parCount and starCount are 0, that means too many ), return false.
Finally, check if starCount >= parCount. These startCount happens after (, and they could be treated as ).
Time Complexity: O(s.length()).
Space: O(1).
AC Java:
class Solution {
public boolean checkValidString(String s) {
if(s == null || s.length() == 0){
return true;
} int parCount = 0;
int starCount = 0;
for(int i = 0; i<s.length(); i++){
char c = s.charAt(i);
if(c == '('){
if(starCount > parCount){
starCount = parCount;
} parCount++;
}else if(c == '*'){
starCount++;
}else{
if(parCount == 0){
if(starCount == 0){
return false;
} starCount--;
}else{
parCount--;
}
}
} return starCount >= parCount;
}
}
When encountering ( or ), it is simple to increment or decrement.
遇到"*". 可能分别对应"(", ")"和empty string 三种情况. 所以计数可能加一, 减一或者不变. 可以记录一个范围[lo, hi].
lo is decremented by * or ).
hi is incremented by * or (.
When hi < 0, that means there are too many ), return false.
If lo > 0 at the end, it means there are too many ( left, return false.
Since lo is decremented by * and ), it could be negative. Thus lo-- should only happen when lo > 0 and maintain lo >= 0.
Note: lo can't be smaller than 0. When hi < 0, return false.
Time Complexity: O(s.length()).
Space: O(1).
AC Java:
class Solution {
public boolean checkValidString(String s) {
if(s == null || s.length() == 0){
return true;
} int lo = 0;
int hi = 0;
for(int i = 0; i<s.length(); i++){
if(s.charAt(i) == '('){
lo++;
hi++;
}else if(s.charAt(i) == ')'){
lo--;
hi--;
}else{
lo--;
hi++;
} if(hi < 0){
return false;
}
lo = Math.max(lo, 0);
} return lo == 0;
}
}