PROBLEM 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 “”.
SOLUTION
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
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public boolean checkValidString(String s) {
//how many min and max open brackets are possible?
int minOpen = 0;
int maxOpen = 0;
for(int i=0; i<s.length(); i++){
char current = s.charAt(i);
//if c is ), we have closed one open bracket, so reduce minOpen and maxOpen both by 1
if(current == ')'){
minOpen--;
maxOpen--;
}
//if c is (, we have one extra open bracket, so increase minOpen and maxOpen both by 1
if(current == '('){
minOpen++;
maxOpen++;
}
//if c is *, it can be empty, open or close
//the minOpen will reduce by 1 if we consider it as closed
//the maxOpen will increase by 1 if we consider it as open
//no change, if we consider it as empty
if(current == '*'){
minOpen--;
maxOpen++;
}
if(maxOpen < 0) return false; //Example: ))((
minOpen = Math.max(0, minOpen); //reset minOpen to 0 as -ve is not possible as min
}
//if the minOpen brackets is 0, which means there is a possible equal number of close brackets
return minOpen == 0;
}
}