Valid ParentheSES #20

20.Valid Parentheses

String

Stack

Hash Table

Problem Statement:

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. A string is valid if opening brackets are closed by the same type of brackets, and opening brackets are closed in the correct order.

Example:

Input:

"({[]})"

→

Output:

true

Each opening bracket has its corresponding closing bracket in the correct order.

Algorithm:

1. Create a stack to track opening brackets
2. Map each closing bracket to its corresponding opening bracket
3. For each character: push if opening bracket, validate and pop if closing
4. Return true if all brackets are matched (stack is empty)

public boolean isValid(String str) {
    Stack<Character> s = new Stack<>();
    Map<Character, Character> map = new HashMap<>();
    map.put(')', '(');
    map.put(']', '[');
    map.put('}', '{');
    
    for (char c : str.toCharArray()) {
        // Push opening brackets to stack
        if (c == '(' || c == '{' || c == '[') {
            s.push(c);
        } else {
            // Check if closing bracket matches last opening bracket
            if (s.empty() || map.get(c) != s.pop()) {
                return false;
            }
        }
    }
    
    return s.isEmpty();
}

Complexity:

Time: O(n) | Space: O(n)