Approach 1: Using stack
An asterisk (*) can be replaced by any any of the following: left parenthesis (, right parenthesis ), or empty string. Let us iterate the string and store occurrences of all left parenthesis ( and asterisks *. When we encounter a right parenthesis, we have to consider the following cases:
- Stack is empty: this means there is no
(or*on the left of the parenthesis so the string is mismatched. - Stack is not empty: this means there is either
(or*on the left. We search for the top most(in the stack and pop it. If there is no(, we consider the rightmost*to be a left parenthesis and pop it from the stack. This way, we only use an*when an opening parenthesis cannot match a closing parenthesis.
This ensures that when we iterate through the whole string, our stack only contains ( and *. Now, there is still one possibility where the string may be mismatched. Consider the string “(()”. Our stack will contain *, *, ( after iterating the whole string. We cannot replace the asterisks * by anything to make the string valid! This is because the left parenthesis occur after the asterisks. Specifically, we have to handle the case where there is **no asterisk on the right of a left parenthesis.
We do this by keeping an asterisks count while popping the stack. If we encounter a left parenthesis and the asterisks count is < 0, we know that the string is invalid.
class Solution {
public:
bool checkValidString(string s) {
stack<int> st, st1;
for (int i=0; i<s.length(); i++) {
if (s[i] == '(' || s[i] == '*')
st.push(s[i]);
else
if (st.empty())
return false;
else {
while (!st.empty() && st.top() == '*') { // find the rightmost occurrence of a left-parenthesis
st1.push(st.top());
st.pop();
}
if (st.empty()) // no left-parenthesis found, pop an asterisk
st1.pop();
else // pop left parenthesis
st.pop();
while (!st1.empty()) { // put back the asterisks in the main stack
st.push(st1.top());
st1.pop();
}
}
}
int sc = 0; // asterisks count
char c;
while (!st.empty()) {
c = st.top();
st.pop();
if (c=='*')
sc++;
else {
if (sc>0) // there is an asterisk on the right of left-parenthesis
sc--;
else // no asterisk on the right of left parenthesis
return false;
}
}
return true;
}
};
Time complexity: O(n)
Space complexity: O(n)
Approach 2: Constance space
Solution by @sansi.
Let us keep track of two variables: “minimum net open parenthesis” (minOpen) and “maximum net open parenthesis” (maxOpen) while iterating the string. When we encounter an asterisk (*), it can act like an opening parenthesis, closing parenthesis or an empty string. To calculate minOpen, we consider * to be a closed parenthesis so that minOpen = minOpen - 1. To calculate maxOpen, we consider * to be an open parenthesis so that maxOpen = maxOpen + 1.
Let us understand why we are keeping track of these variables. Consider the string “(**())”. Let us iterate character by character:
1. `(`: minOpen = 1, maxOpen = 1
2. `*`: Now, the string can become `()` or `(` or `((`. So net opening parenthesis can be 0, 1 or 2. Notice that this the range [minOpen, maxOpen] where minOpen=0 and maxOpen=1.
3. `*`: For each case in step 2, we can diverge the string into 3 cases again. minOpen = -1 and maxOpen = 3. You will notice that these strings will have net opening bracket in the range [minOpen, maxOpen]. For example, strings with opening parenthesis = 1 would be "(" or "()(" or "(()". Since minOpen = -1 does not make sense to us, we will discard those strings and keep minOpen = 0.
4. `(`: minOpen = 1, maxOpen = 4
5. `)`: minOpen = 0, maxOpen = 3
6. `)`: minOpen = 0 (discarding strings with minOpen = -1), maxOpen = 2
When do we know a string is invalid?
A string is clearly invalid when maxOpen goes below zero while iterating the string (that means all routes have more ) than ( –> all routes are invalid –> stop and return false) OR minOpen is not equal to zero after we finish iterating the string.
public boolean checkValidString(String s) {
int low = 0; // low is minOpen
int high = 0; // high is maxOpen
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
low++;
high++;
} else if (s.charAt(i) == ')') {
if (low > 0) {
low--;
}
high--;
} else {
if (low > 0) {
low--;
}
high++;
}
if (high < 0) {
return false;
}
}
return low == 0;
}
Time complexity: O(n)
Space complexity: O(1)