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""
.
LeetCode Problem - 678
class Solution {
public boolean checkValidString(String s) {
// Variables to track open and closed brackets
int openBracket = 0;
int closedBracket = 0;
// Length of the string
int length = s.length()-1;
// Loop through the string
for(int i=0; i<=length; i++){
// If character is '(' or '*', increment openBracket count
if(s.charAt(i) == '(' || s.charAt(i) == '*'){
openBracket++;
} else
// If character is ')' decrement openBracket count
openBracket--;
// If character at the end of the string is ')' or '*', increment closedBracket count
if(s.charAt(length - i) == ')' || s.charAt(length - i) == '*'){
closedBracket++;
} else
// If character at the end of the string is '(' decrement closedBracket count
closedBracket--;
// If either openBracket or closedBracket count is negative, return false
if(openBracket < 0 || closedBracket < 0){
return false;
}
}
// If loop completes, return true
return true;
}//method
} // main