Solving the ‘Valid Parentheses’ on LeetCode: Java Solutions Walkthrough

The ‘Valid Parentheses’ problem on LeetCode is a common question that checks your understanding of stack data structures. It’s categorized under the “Easy” problems, but solving it efficiently and understanding its intricacies is essential for further exploration into more complex problems. In this post, we’ll go through three common solution examples and conclude by comparing these solutions to determine the most efficient one. After the conclusion, each solution is presented with detailed commented code and a step-by-step explanation to ensure the concepts and implementations are clear and understandable.

Problem Statement

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

• Open brackets must be closed by the same type of brackets.
• Open brackets must be closed in the correct order.
• Every close bracket has a corresponding open bracket of the same type.

Function Signature in Java:

   public boolean isValid(String s) {
        
    }

Example 1:

Input: s = “()” Output: true

Example 2:

Input: s = “()[]{}” Output: true

Example 3:

Input: s = “(]” Output: false

Solution 1: Using Stack

Explanation

In this approach, we utilize a stack data structure to keep track of the opening brackets. Whenever we encounter a closing bracket, we check if it correctly corresponds to the top element of the stack (the last opened bracket).

Java Code:

import java.util.Stack;

class Solution {
    public 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 open = stack.pop();
                if (c == ')' && open != '(') return false;
                if (c == '}' && open != '{') return false;
                if (c == ']' && open != '[') return false;
            }
        }
        return stack.isEmpty();
    }
}

Time Complexity

O(n), where n is the number of characters in the string.

Space Complexity

O(n). The space complexity is O(n) because a stack is used, and in the worst case, all characters in the string will be stored in the stack, which grows with the input size.

Solution 2: Using HashMap and Stack

Explanation

In this solution, we use a HashMap to maintain the mappings of opening and closing brackets. This makes our code more concise and readable.

Java Code:

import java.util.*;

class Solution {
    public boolean isValid(String s) {
        Map<Character, Character> mappings = new HashMap<>();
        mappings.put(')', '(');
        mappings.put('}', '{');
        mappings.put(']', '[');

        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (mappings.containsKey(c)) {
                char topElement = stack.isEmpty() ? '#' : stack.pop();
                if (topElement != mappings.get(c)) {
                    return false;
                }
            } else {
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}

Time Complexity

O(n), where n is the number of characters in the string.

Space Complexity

O(n). The space complexity is O(n) because a stack and a hashmap are used. In the worst case, all characters will be stored in the stack and the hashmap, which grow with the input size.

Solution 3: Optimized Stack Solution

Explanation

This solution optimizes the stack approach by checking for specific conditions to immediately return false, reducing the number of operations needed.

Java Code:

class Solution {
    public boolean isValid(String s) {
        if (s.length() % 2 != 0) return false;

        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(')');
            } else if (c == '{') {
                stack.push('}');
            } else if (c == '[') {
                stack.push(']');
            } else if (stack.isEmpty() || stack.pop() != c) {
                return false;
            }
        }
        return stack.isEmpty();
    }
}

Time Complexity

O(n), where n is the number of characters in the string.

Space Complexity

O(n). The space complexity is O(n) because a stack is used, and in the worst case, all characters will be stored in the stack, which grows with the input size.

Conclusion

After exploring the three different methods to solve the Valid Parentheses Problem:

1. Using Stack: A straightforward stack approach which is easy to understand and implement.
2. Using HashMap and Stack: Uses HashMap for cleaner and more readable code.
3. Optimized Stack Solution: Performs specific checks to reduce the number of operations.

All approaches have a time and space complexity of O(n). The choice of approach depends on the preference for code readability and conciseness. The second approach using HashMap and Stack offers more readability and clean code, whereas the third approach optimizes the number of operations by adding specific checks.

1. GeeksforGeeks: Valid Parentheses Problem
2. GeeksforGeeks: Stack Data Structure in Java

Commented Code and Step-by-Step Explanations

Solution 1: Using Stack

class Solution {
    public boolean isValid(String s) {
        // Create a Stack to keep track of the opening brackets.
        Stack<Character> stack = new Stack<>();
        // Iterate through each character in the input string.
        for (char c : s.toCharArray()) {
            // If it's an opening bracket, push onto the stack.
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                // If the stack is empty, there's no matching opening bracket.
                if (stack.isEmpty()) return false;
                // Pop the last opening bracket from the stack.
                char open = stack.pop();
                // Check if the popped bracket matches with the closing bracket.
                if (c == ')' && open != '(') return false;
                if (c == '}' && open != '{') return false;
                if (c == ']' && open != '[') return false;
            }
        }
        // If stack is empty, all the opening brackets had a matching closing pair.
        return stack.isEmpty();
    }
}

Step-by-Step Explanation

1. Initialize Stack: Create a Stack to keep track of opening brackets.
2. Iterate Through String: Iterate through each character in the input string.
3. Push Opening Brackets: If it’s an opening bracket ((, {, [), push it onto the stack.
4. Check Closing Brackets: If a closing bracket is encountered, pop the last opening bracket from the stack and check if they match.
5. Return Result: After processing all characters, if the stack is empty, return true. Otherwise, return false.

Solution 2: Using HashMap and Stack

class Solution {
    public boolean isValid(String s) {
        // Create a HashMap to store the mappings of brackets.
        Map<Character, Character> mappings = new HashMap<>();
        mappings.put(')', '(');
        mappings.put('}', '{');
        mappings.put(']', '[');

        // Create a Stack to keep track of opening brackets.
        Stack<Character> stack = new Stack<>();
        // Iterate through each character in the input string.
        for (char c : s.toCharArray()) {
            // If it's a closing bracket.
            if (mappings.containsKey(c)) {
                // Pop the last opening bracket from the stack.
                char topElement = stack.isEmpty() ? '#' : stack.pop();
                // Check if the popped bracket matches with the closing bracket.
                if (topElement != mappings.get(c)) {
                    return false;
                }
            } else {
                // If it's an opening bracket, push onto the stack.
                stack.push(c);
            }
        }
        // If stack is empty, all the opening brackets had a matching closing pair.
        return stack.isEmpty();
    }
}

Step-by-Step Explanation

1. Initialize HashMap and Stack: Create a HashMap to store bracket mappings and a Stack to keep track of opening brackets.
2. Iterate Through String: Iterate through each character in the input string.
3. Handle Closing Brackets: If it’s a closing bracket, pop the last opening bracket from the stack and check if they match.
4. Handle Opening Brackets: If it’s an opening bracket, push it onto the stack.
5. Return Result: If the stack is empty after processing all characters, return true. Otherwise, return false.

Solution 3: Optimized Stack Solution

class Solution {
    public boolean isValid(String s) {
        // If the length of string is odd, it cannot be valid.
        if (s.length() % 2 != 0) return false;

        // Create a Stack to keep track of opening brackets.
        Stack<Character> stack = new Stack<>();
        // Iterate through each character in the input string.
        for (char c : s.toCharArray()) {
            // Push the corresponding closing bracket for each opening bracket onto the stack.
            if (c == '(') {
                stack.push(')');
            } else if (c == '{') {
                stack.push('}');
            } else if (c == '[') {
                stack.push(']');
            } else if (stack.isEmpty() || stack.pop() != c) {
                // If stack is empty or top does not match with the closing bracket, return false.
                return false;
            }
        }
        // If stack is empty, all the opening brackets had a matching closing pair.
        return stack.isEmpty();
    }
}

Step-by-Step Explanation

1. Check Length: If the length of string is odd, return false as it cannot be valid.
2. Initialize Stack: Create a Stack to keep track of brackets.
3. Iterate Through String: Iterate through each character in the input string.
4. Push Closing Brackets: Push the corresponding closing bracket onto the stack for each opening bracket encountered.
5. Handle Closing Brackets: If a closing bracket is encountered, check if the stack is empty or the top of the stack matches with the bracket. If not, return false.
6. Return Result: After processing all characters, if the stack is empty, return true. Otherwise, return false.