Java Coding Test Course, Stack and Queue

Problem 1: Valid Parentheses

This problem is to determine if a given string is a valid parentheses string.
A valid parentheses string means that every open parenthesis is properly closed by a corresponding closing parenthesis and follows the correct order.
For example, “()”, “()[]{}”, “{[()]}” are valid, but “(]”, “([)]”, “{)” are not valid.

Problem Description

Implement a function to determine if the given input string s is a valid parentheses string.
A valid parentheses string must satisfy the following conditions:

Every open parenthesis must have a corresponding closing parenthesis.
Open parentheses must be properly ordered.

Input Examples

“()” -> true
“()[]{}” -> true
“{[()]}” -> true
“(]” -> false
“([)]” -> false
“{)” -> false

Solution Method

This problem can be solved using a stack.
The stack (FILO: First In Last Out) structure is very useful for operations involving parentheses. The process is as follows.

Iterate through the string from left to right.
When encountering an open parenthesis ((, {, [), push it onto the stack.
When encountering a closing parenthesis (), }, ]), pop from the stack and check if it forms a pair with the most recently opened parenthesis.
After processing the entire string, if the stack is empty, it is considered a valid parentheses string.

Java Code Implementation

            
            import java.util.Stack;

            public class ValidParentheses {
                public static boolean isValid(String s) {
                    Stack stack = new Stack<>();
                    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();
                }

                public static void main(String[] args) {
                    System.out.println(isValid("()")); // true
                    System.out.println(isValid("()[]{}")); // true
                    System.out.println(isValid("{[()]}")); // true
                    System.out.println(isValid("(]")); // false
                    System.out.println(isValid("([)]")); // false
                    System.out.println(isValid("{)")); // false
                }
            }

Time Complexity

The time complexity of this algorithm is O(n).
Here, n is the length of the string. Since we are using a stack, in the worst case, when there are n open parentheses, there can be n pushes and n pops.

Space Complexity

The space complexity is also O(n).
As the stack can hold a maximum of n open parentheses, the worst-case space complexity is O(n).

Summary of the Problem-Solving Process

In order to solve this problem, we used a stack to track open parentheses and checked each closing parenthesis by popping from the stack.
This method is very efficient for checking the validity of parentheses, and the same principle can be applied to check the validity of other types of parentheses.

Tips for Valid Coding Tests

Stacks and queues are frequently used data structures in coding tests.
It is important to become familiar with how to use stacks and queues through various problems.
Learn common patterns and tricks, and practice various variations to enhance your problem-solving skills.