58. Valid Parenthesis String[중간]
30 Jul 2020 | Daily Algorithms
-
Since * can be used as 3 kinds of char, if we do backtrack the complexity can blow up if the string is ***…. We need to find **a non-trivial method.(Nontrivial is a favorite word among programmers and computer people for describing any task that is not quick and easy to accomplish. It may mean “extremely” difficult and time consuming.)
-
Without * , we can just use a number to indicate the unmatch (, ( will increment it and ) will decrement it. We don’t want this number less than 0 all the time and it should be 0 when all the string has been matched.
-
When * is introduced, the number becomes a range, indicating the number of possible unmatched ( found. One * just expand the range by 1. And we can use the same principle to check if the criteria above is within the range.
class Solution {
public:
bool checkValidString(string s) {
int lower = 0, upper = 0;
for(auto c : s )
{
if(c=='(')
{
lower++;
upper++;
}
else if( c == ')')
{
lower--;
upper--;
}
else // enconuter '*'
{
lower--;
upper++;
}
lower = max(lower,0);
if(upper<0) // unmatched ')' found in the middle of string
return false;
}
return lower == 0;
}
};
-
Since * can be used as 3 kinds of char, if we do backtrack the complexity can blow up if the string is ***…. We need to find **a non-trivial method.(Nontrivial is a favorite word among programmers and computer people for describing any task that is not quick and easy to accomplish. It may mean “extremely” difficult and time consuming.)
-
Without * , we can just use a number to indicate the unmatch (, ( will increment it and ) will decrement it. We don’t want this number less than 0 all the time and it should be 0 when all the string has been matched.
-
When * is introduced, the number becomes a range, indicating the number of possible unmatched ( found. One * just expand the range by 1. And we can use the same principle to check if the criteria above is within the range.
class Solution {
public:
bool checkValidString(string s) {
int lower = 0, upper = 0;
for(auto c : s )
{
if(c=='(')
{
lower++;
upper++;
}
else if( c == ')')
{
lower--;
upper--;
}
else // enconuter '*'
{
lower--;
upper++;
}
lower = max(lower,0);
if(upper<0) // unmatched ')' found in the middle of string
return false;
}
return lower == 0;
}
};
Comments