LeetCode — 20. Valid Parentheses

In this blog, we explore a Java solution to the classic problem of validating a string of parentheses for balanced brackets. The solution employs a stack data structure to ensure that each opening bracket has a corresponding closing bracket in the correct order.

The Approach

The core idea behind this solution is to use a stack to keep track of the brackets. When an opening bracket is encountered, its corresponding closing bracket is pushed onto the stack. When a closing bracket is found, it is matched against the element at the top of the stack. If they match, the process continues; otherwise, the string is immediately deemed invalid.

Key Components of the Solution:

A Map for Bracket Matching: A HashMap is used to map each opening bracket to its corresponding closing bracket. This allows for easy lookup and ensures that the code remains clean and understandable.

Stack for Tracking: A Stack is used to keep track of expected closing brackets. This choice of data structure is crucial because it naturally supports the LIFO (Last In, First Out) property needed for valid bracket matching.

Algorithm Steps:

1. Iterate over each character in the string.
2. If the character is an opening bracket, push its corresponding closing bracket onto the stack.
3. If it’s a closing bracket, check if the stack is empty or if the top of the stack does not match the current character. If either condition is true, the string is invalid.
4. After processing all characters, if the stack is empty, the string is valid; otherwise, it’s invalid.

Example:

Given the string “{[()]}”, the solution correctly identifies it as valid, while it flags “{[(])}” as invalid.

Time and Space Complexity

Time Complexity: O(n), where n is the length of the input string. Each character in the string is processed exactly once, making the algorithm linear in the size of the input.

Space Complexity: O(n) in the worst case, when all characters are opening brackets, and thus all of them get pushed onto the stack. However, in the average case, the space complexity could be less than O(n), depending on the number of opening brackets.

JavaScript version

class Solution {
    public boolean isValid(String s) {

        Map<Character, Character> map = new HashMap<>();
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');

        Stack<Character> stack = new Stack<>();

        char[] sArr = s.toCharArray();

        for (char bracketChar : sArr) {
            if (map.containsKey(bracketChar)) {
                stack.push(map.get(bracketChar));
                continue;
            }

            if (stack.isEmpty() || stack.pop() != bracketChar)
                return false;
        }

        return stack.isEmpty();
    }
}

Java version

class Solution {
    public boolean isValid(String s) {

        Map<Character, Character> map = new HashMap<>();
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');

        Stack<Character> stack = new Stack<>();

        char[] sArr = s.toCharArray();

        for (char bracketChar : sArr) {
            if (map.containsKey(bracketChar)) {
                stack.push(map.get(bracketChar));
                continue;
            }

            if (stack.isEmpty() || stack.pop() != bracketChar)
                return false;
        }

        return stack.isEmpty();
    }
}