Valid Parentheses

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

An input string is valid if:

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

Example 1:

Input: s = ”()” Output: true

Example 2:

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

Example 3:

Input: s = ”(]” Output: false

Example 4:

Input: s = ”([])” Output: true

Example 5:

Input: s = ”([)]” Output: false

Constraints:

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

Approach: Stack (Optimal Solution)

Algorithm

1. Create a stack to store open brackets
2. Iterate through each character in the string
3. If the character is an open bracket ((, {, [), push it onto the stack
4. If the character is a close bracket, check if the stack is empty or if the top of the stack matches the close bracket
5. If it doesn’t match, return false
6. After processing all characters, the string is valid only if the stack is empty

Key Insight

The most recently opened bracket must be closed first (LIFO order). A stack naturally models this nesting behavior, so matching each close bracket against the top of the stack verifies both correct type and correct order.

Time & Space Complexity

• Time Complexity: O(n) - single pass through the string
• Space Complexity: O(n) - stack stores up to n/2 open brackets in the worst case

Java Implementation

import java.util.Stack;

public class ValidParentheses {

    /**
     * Determine if a string of brackets is valid.
     * @param s String containing only bracket characters
     * @return true if the brackets are correctly matched, false otherwise
     */
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {
            // Push open brackets onto the stack
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                // Close bracket must match the top of the stack
                if (stack.isEmpty()) {
                    return false;
                }
                char top = stack.pop();
                if ((c == ')' && top != '(') ||
                    (c == '}' && top != '{') ||
                    (c == ']' && top != '[')) {
                    return false;
                }
            }
        }

        // Valid only if all open brackets were closed
        return stack.isEmpty();
    }

    // Test method
    public static void main(String[] args) {
        // Test case 1
        System.out.println("Input: s = \"()\"");
        System.out.println("Output: " + isValid("()")); // Expected: true

        // Test case 2
        System.out.println("Input: s = \"()[]{}\"");
        System.out.println("Output: " + isValid("()[]{}")); // Expected: true

        // Test case 3
        System.out.println("Input: s = \"(]\"");
        System.out.println("Output: " + isValid("(]")); // Expected: false

        // Test case 4
        System.out.println("Input: s = \"([])\"");
        System.out.println("Output: " + isValid("([])")); // Expected: true

        // Test case 5
        System.out.println("Input: s = \"([)]\"");
        System.out.println("Output: " + isValid("([)]")); // Expected: false
    }
}

Example Walkthrough

For s = "([)]":

1. c=’(’: push ’(’ → stack = [ ( ]
2. c=’[’: push ’[’ → stack = [ ( , [ ]
3. c=’)’: top is ’[’, which does not match ’)’. Return false

For s = "([])":

1. c=’(’: push ’(’ → stack = [ ( ]
2. c=’[’: push ’[’ → stack = [ ( , [ ]
3. c=’]’: top is ’[’, matches ’]’. Pop → stack = [ ( ]
4. c=’)’: top is ’(’, matches ’)’. Pop → stack = [ ]
5. Stack is empty, return true

Alternative Implementation with HashMap

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public static boolean isValidWithMap(String s) {
    Map<Character, Character> mapping = new HashMap<>();
    mapping.put(')', '(');
    mapping.put('}', '{');
    mapping.put(']', '[');

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

Key Insights

1. LIFO Matching: The stack naturally handles nested brackets by matching the most recent open bracket first
2. Type Matching: Ensures close brackets match open brackets of the same type
3. Edge Cases: Handles trailing open brackets (stack not empty) and leading close brackets (stack empty)
4. Correct Ordering: Detects incorrectly ordered brackets like ”([)]” because the top of the stack won’t match

The stack-based approach is the optimal solution for this problem, providing linear time and space complexity.