Valid Parentheses

Problem Statement

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

Approach: Stack

We can use a Stack data structure to keep track of the open brackets we have seen so far. Since the most recently opened bracket must be the first one to be closed, a LIFO (Last-In-First-Out) structure is perfectly suited for this problem.

1. Initialize an empty stack.
2. Use a Hash Map to store the mappings of closing brackets to their corresponding opening brackets for $O(1)$ lookups.
3. Iterate through each character c in the string s:
   • If c is a closing bracket (it exists in our Hash Map):
     • Pop the top element from the stack. If the stack is empty, use a dummy value (e.g., '#').
     • Check if the popped element matches the corresponding opening bracket from the Hash Map.
     • If it doesn’t match, the string is invalid, return false.
   • If c is an opening bracket:
     • Push it onto the stack.
4. After processing all characters, if the stack is empty, it means all opening brackets were properly closed. Return true.
5. If the stack is not empty, there are unmatched opening brackets left. Return false.

Solution

/**
 * @param {string} s
 * @return {boolean}
 */
function isValid(s) {
    const stack = [];
    const map = {
        ')': '(',
        '}': '{',
        ']': '['
    };
    
    for (let i = 0; i < s.length; i++) {
        const char = s[i];
        
        if (map[char]) {
            // It's a closing bracket
            const topElement = stack.length > 0 ? stack.pop() : '#';
            if (map[char] !== topElement) {
                return false;
            }
        } else {
            // It's an opening bracket
            stack.push(char);
        }
    }
    
    return stack.length === 0;
}

Complexity Analysis

• Time Complexity: $O(n)$ where $n$ is the length of the string s. We traverse the string exactly once. Pushing and popping from the stack takes $O(1)$ time, as do Hash Map lookups.
• Space Complexity: $O(n)$ in the worst case when the string consists of only opening brackets (e.g., "(((((("), the stack will store all $n$ characters. The Hash Map always stores a constant 3 key-value pairs, which takes $O(1)$ space.