Daily Question – 678. Valid Parenthesis String

Description: https://leetcode.com/problems/valid-parenthesis-string/description/?envType=daily-question&envId=2024-04-07

Approach:

My initial approach is quite straightforward:

Using stack to save the index of both ‘(‘ and ‘*’.

I iterate over each character of the string from left to right. Once I encounter the character ‘)’, I first pop the ‘(‘ stack and then the ‘*’ stack.

If both stacks are empty and there are still ‘)’ characters remaining, I return false.

After the iteration loop, for the remaining ‘(‘ stack, if any index is larger than the indices in the ‘*’ stack, I return false.

Code:

class Solution {
    public boolean checkValidString(String s) {
        Stack<Integer> stack = new Stack<>();
        Stack<Integer> star = new Stack<>();
        int x, y;
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '(') stack.push(i);
            if (chars[i]  == '*') star.push(i);
            if (chars[i]  == ')') {
                if (!stack.isEmpty()) stack.pop(); else if (!star.isEmpty()) star.pop(); else return false;
            }
        }
        while(!stack.isEmpty()) {
            x = stack.pop();
            if (!star.isEmpty()) y = star.pop(); else return false;
            if (x > y) return false;
        }
        return true;
    }
}

Leetcode Solution:

From: https://leetcode.com/problems/valid-parenthesis-string/solutions/4985006/96-98-easy-solution-with-explanation/

public class Solution {
    public boolean checkValidString(String s) {
        int leftMin = 0, leftMax = 0;

        for (char c : s.toCharArray()) {
            if (c == '(') {
                leftMin++;
                leftMax++;
            } else if (c == ')') {
                leftMin--;
                leftMax--;
            } else {
                leftMin--;
                leftMax++;
            }
            if (leftMax < 0) return false;
            if (leftMin < 0) leftMin = 0;
        }
        
        return leftMin == 0;
    }
}