0678-valid-parenthesis-string.java

classSolution {

publicbooleancheckValidString(Strings) {
intcount = 0;
Stack<Integer> op = newStack<>();
Stack<Integer> st = newStack<>();

for (inti = 0; i < s.length(); ++i) {
if (s.charAt(i) == '(') op.push(i); // index of opening
elseif (s.charAt(i) == ')') {
if (op.size() > 0) op.pop(); // if we have brackets
elseif (st.size() > 0) st.pop(); // if not brackets do we have stars
elsereturnfalse; // a closing bracket without opening and star
 } elsest.push(i); // index of star
 }
// if we left with some opening bracket that over stars con cover up
while (op.size() > 0 && st.size() > 0) {
if (op.peek() > st.peek()) returnfalse;
op.pop();
st.pop();
 }

returnop.size() == 0;
 }
}

// Time complexity: O(n)
// Space complexity: O(1)
classSolution2 {

publicbooleancheckValidString(Strings) {
intlow = 0, high = 0;
for (inti = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
low++;
high++;
 } elseif (s.charAt(i) == ')') {
if (low > 0) {
low--;
 }
high--;
 } else {
if (low > 0) {
low--;
 }
high++;
 }
if (high < 0) {
returnfalse;
 }
 }
returnlow == 0;
 }
}