Problem: 678. Valid Parenthesis String
First Approach
Can utilize a similar method like validating parenthesis.
Loop through each char c in the string s and check:
- if
c == *, increasecountStar - if
c == (, increasecountLeft - if
c == ), decreasecountLeftifcountLeft> 0. otherwise, ifcountStar> 0, decrease it, else return false.
At the end, if countStar >= countLeft, return true, else, return false.
This may sound like a good approach but this will fail since there is another restriction that we have not taken into consideration:
Left parenthesis '(' must go before the corresponding right parenthesis ')'.
That means if there is a star and a left parenthesis, the star must come after.
Correct Approach
We will utilize Stack and Queue to keep track of the index of the left parenthesis and the stars.
After removing all the right parenthesis like mentioned above, we will check the positions of the stars and left parenthesis to make sure it meet the requirements
Here is a simple explanation:
- used stack for left paren and queue for star?
- will store the int value (the index of the parent and star only)
- if there is some right paren without left paren remove star from the top of the queue (smallest positions)
when there are only left paren left.
- pop from the end => get the largest, if it does not satisfy => false
- convert queue into stack for popped out
- keep doing until empty
class Solution {
public boolean checkValidString(String s) {
Queue<Integer> starQ = new LinkedList<>();
Stack<Integer> leftS = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '*') {
starQ.add(i);
} else if (c == '(') {
leftS.add(i);
} else {
// ) only
if (!leftS.isEmpty()) {
leftS.pop();
} else {
if (!starQ.isEmpty()) {
starQ.remove();
} else {
return false;
}
}
}
}
if (leftS.isEmpty()) {
return true;
} else if (starQ.isEmpty()) {
// this means still has left but no star
return false;
} else {
// convert
Stack<Integer> starS = new Stack<>();
while (!starQ.isEmpty()) {
starS.add(starQ.remove());
}
while (!starS.isEmpty() && !leftS.isEmpty()) {
int left = leftS.pop();
int star = starS.pop();
if (star < left) {
return false;
}
}
if (leftS.isEmpty()) {
return true;
}
return false;
}
}
}
Top comments (0)