Valid Parentheses

Given a string containing characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid. The string is considered valid if:

1. Open brackets are closed by the same type of brackets.
2. Open brackets are closed in the correct order.

Example of a valid string: {[()]}

Example of an invalid string: ([)]

Validating Complex Parentheses Combinations: A Java Solution

Introduction

Validating a string of mixed parentheses types, including curly braces {}, square brackets [], and parentheses (), adds a layer of complexity to the classic problem of checking for balanced parentheses. This scenario is common in many programming and data science applications, such as parsing expressions or analyzing code syntax.

In this blog post, we’ll extend our approach to handle mixed types of parentheses, ensuring that each opening bracket is properly matched with its corresponding closing counterpart in the correct order.

Problem Statement

Given a string containing characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid. The string is considered valid if:

1. Open brackets are closed by the same type of brackets.
2. Open brackets are closed in the correct order.

Example of a valid string: {[()]}

Example of an invalid string: ([)]

Approach: Utilizing a Stack

While the balance counting method works well for single types of parentheses, mixed types require tracking the order and type of brackets. For this, we use a stack data structure to push opening brackets and pop them when a matching closing bracket is encountered.

Here’s the step-by-step approach:

1. Initialize a Stack: Use a stack to keep track of opening brackets.
2. Iterate Through the String: For each character in the string:
   • If it’s an opening bracket, push it onto the stack.
   • If it’s a closing bracket, check if the stack is empty or if the top of the stack doesn’t match the corresponding opening bracket. If either condition is true, the string is invalid.
3. Final Check: After iterating through the string, if the stack is empty, then all brackets were properly matched and closed, indicating a valid string. Otherwise, the string is invalid.

Implementation in Java

Here’s how to implement this solution in Java:

import java.util.Stack;

public class Solution {

    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (isOpenBracket(c)) {
                stack.push(c);
            } else {
                if (stack.isEmpty() || !isMatchingBracket(stack.pop(), c)) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    private boolean isOpenBracket(char bracket) {
        return bracket == '(' || bracket == '{' || bracket == '[';
    }

    private boolean isMatchingBracket(char open, char close) {
        return (open == '(' && close == ')') ||
               (open == '{' && close == '}') ||
               (open == '[' && close == ']');
    }
}