Solving the Valid Parentheses Problem in Java

Let's solve this problem using stack-based parsing with different code structures to improve our logical thinking and DSA skills.

We are given a string s containing only the characters '(', ')', '{', '}', '[' and ']'. We need to check whether it is a valid string based on the following validation rules:

• Open brackets must be closed by the same type of bracket.
  
• Open brackets must be closed in the correct order.
• Every closing bracket must have a corresponding opening bracket of the same type.

We will solve this problem using a stack-based parsing approach, which means for every closing bracket, we check if there is a corresponding opening bracket in the stack.

Here, we present three Java methods that solve the problem using the same logic but different coding styles and data structures, each improving efficiency step by step.

Here is the code for our first method, which uses an ArrayDeque and a for loop.

public static boolean isValid1(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;

            char top = stack.pop();
            if ((c == ')' && top != '(') || (c == '}' && top != '{') || (c == ']' && top != '[')) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

In this code, we push opening brackets into the stack. For each closing bracket, we pop from the stack to check if it matches, ensuring the stack is not empty before popping.

Here is the code for the second method, where we avoid extra memory use and reduce unnecessary checks.

public static boolean isValid2(String s) {
    Stack<Character> st = new Stack<>();
    for(int i=0;i<s.length();i++){
        char c = s.charAt(i);
        if(c == '(') st.push(')');
        else if(c == '{') st.push('}');
        else if(c == '[') st.push(']');
        else if(st.isEmpty() || c != st.pop()) return false;
    }
    return st.isEmpty();
}

In this code, we push the expected closing brackets into the stack instead of the opening ones, then check if the closing brackets match as we iterate.

Finally, in the third method, we improve efficiency by implementing a custom stack using a char array and an integer pointer.

public boolean isValid3(String s) {
    if ((s.length() & 1) == 1) return false;
    char[] p  = new char[s.length()];
    int top = -1;
    char last;
    for (int i=0; i<s.length(); i++) {
        char ch = s.charAt(i);
    	switch (ch) {
    		case '(': p[++top] = ')'; break;
    		case '{': p[++top] = '}'; break;
    		case '[': p[++top] = ']'; break;
    		default: 
    		if (top == -1 || ch != p[top--]) return false;
    	}
    }
    return top == -1;
}

This approach avoids Java collection overhead, method calls, and auto-boxing, benefits from switch-case optimization, and includes an early exit for inputs with odd length.

So this is the stack-based technique to check for valid parentheses demonstrated through different methods. The time complexity of each solution is O(n).

I hope you enjoyed solving this problem with me and understood how the stack helps in matching brackets. Customizing the stack further improves efficiency, and I hope you found this post useful for your DSA skills.

Thanks for reading! 🤝 Happy Coding! ✨