Valid Parentheses easy

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.

Example 1:

Input: s = "()" Output: true

Example 2:

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

Example 3:

Input: s = "(]" Output: false

Example 4:

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

Example 5:

Input: s = "{[]}" Output: true

Steps:

1. Use a Stack: We'll utilize a stack data structure to keep track of opening brackets.
2. Iterate through the string: Process each character in the input string s.
3. Opening Bracket: If the character is an opening bracket ('(', '[', or '{'), push it onto the stack.
4. Closing Bracket: If the character is a closing bracket (')', ']', or '}'):
   • Check if the stack is empty. If it is, the string is invalid (no matching opening bracket).
   • Pop the top element from the stack.
   • Check if the popped element matches the closing bracket. If not, the string is invalid.
5. End of String: After iterating through the entire string:
   • If the stack is empty, it means all opening brackets have been correctly closed, and the string is valid.
   • If the stack is not empty, it means there are unmatched opening brackets, and the string is invalid.

Explanation:

The algorithm leverages the Last-In-First-Out (LIFO) property of the stack. Opening brackets are pushed onto the stack as they are encountered. When a closing bracket is encountered, the corresponding opening bracket must be at the top of the stack to ensure correct order and matching type. If the stack is empty at the end, it implies a perfect balance of opening and closing brackets.

Code:

function isValid(s: string): boolean {
    const stack: string[] = [];
    const bracketMap: { [key: string]: string } = {
        ')': '(',
        '}': '{',
        ']': '['
    };

    for (let i = 0; i < s.length; i++) {
        const char = s[i];
        if (char === '(' || char === '{' || char === '[') {
            stack.push(char);
        } else if (char === ')' || char === '}' || char === ']') {
            if (stack.length === 0) {
                return false; // Unmatched closing bracket
            }
            const top = stack.pop();
            if (top !== bracketMap[char]) {
                return false; // Mismatched brackets
            }
        }
    }

    return stack.length === 0; // True if stack is empty (all brackets matched)
};

Complexity:

• Time Complexity: O(n), where n is the length of the string. We iterate through the string once.
• Space Complexity: O(n) in the worst case. The stack can grow to a size equal to the length of the string if the string contains only opening brackets. In the best case (empty string or perfectly balanced), the space complexity is O(1).