Valid Parentheses - Java Solution

1. Introduction

In this post, we'll tackle the "Valid Parentheses" problem, a common challenge in string processing and stack usage. The problem involves determining if a string of parentheses, braces, and brackets is valid, based on the order and type of each bracket.

Problem

Given a string s containing characters '(', ')', '{', '}', '[' and ']', the task is to check if the input string is valid. An input string is valid if:

- Open brackets are closed by the same type of brackets.

- Open brackets are closed in the correct order.

- Every close bracket has a corresponding open bracket of the same type.

Examples:

- Input: s = "()"

Output: true

- Input: s = "()[]{}"

Output: true

- Input: s = "(]"

Output: false

2. Solution Steps

1. Use a stack to keep track of opening brackets.

2. Iterate through the string s.

3. If the current character is an opening bracket, push it onto the stack.

4. If it's a closing bracket, check if it matches the top element of the stack.

- If it matches, pop the top element from the stack.

- If it doesn't match or the stack is empty, return false.

5. After the iteration, if the stack is empty, return true; otherwise, return false.

3. Code Program

import java.util.Stack;

public class ValidParentheses {
    public static void main(String[] args) {
        String s = "()[]{}";
        System.out.println(isValid(s)); // Test the function
    }

    // Function to determine if the input string is valid
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) return false;
                char top = stack.peek();
                if ((c == ')' && top != '(') || (c == '}' && top != '{') || (c == ']' && top != '[')) {
                    return false;
                }
                stack.pop();
            }
        }

        return stack.isEmpty();
    }
}

Output:

true

Explanation:

1. isValid: This function checks whether a string made of parentheses, braces, and brackets is valid.

2. It uses a Stack to keep track of opening brackets. Each time an opening bracket is encountered, it's pushed onto the stack.

3. For every closing bracket, the function checks if it matches the type of the top element in the stack.

4. If there's a match, the top element is popped. If not, or if the stack is empty (indicating an unmatched closing bracket), the function returns false.

5. Finally, the string is valid if the stack is empty at the end of the iteration, ensuring all opening brackets have been matched and closed correctly.

6. This method effectively validates the string using stack properties, offering a straightforward and efficient solution.