20. Valid Parentheses

Description

Difficulty: Easy

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 <= 10⁴
• s consists of parentheses only '()[]{}'.

Solution

The core principle employed is that every opening bracket must have a corresponding closing bracket of the same type, and they must be correctly nested. This "Last-In, First-Out" (LIFO) requirement naturally leads to the use of a stack data structure.

• Initialization: An empty stack is initialized to store encountered opening brackets.

• Iterative Processing: The input string is traversed sequentially, character by character.

  • Opening Brackets: Upon encountering an opening bracket ((, {, or [ ), it is pushed onto the stack. This action records its presence, signifying an expectation for its future closure.

  • Closing Brackets: Upon encountering a closing bracket (), }, or ] ):

    • The algorithm first verifies if the stack is empty. An empty stack at this point indicates an unpartnered closing bracket, rendering the string invalid.

    • If the stack is not empty, the top element is popped. This element represents the most recently opened and currently unclosed bracket.

    • A type-matching validation is then performed: the popped opening bracket must correspond precisely to the current closing bracket (e.g., ( must be paired with )). A mismatch invalidates the string.

• Final Validation: After processing all characters in the string, the algorithm performs a conclusive check:

  • If the stack is empty, it signifies that all opening brackets were successfully matched and closed, confirming the string's validity.

  • If the stack is non-empty, it indicates the presence of unclosed opening brackets, rendering the string invalid.

Code

import java.util.ArrayDeque;

class Solution {
    public boolean isValid(String s) {
        ArrayDeque<Character> parentheses = new ArrayDeque<Character>();

        for (char c : s.toCharArray()) {
            switch (c) {
                case '(':
                case '{':
                case '[':
                    parentheses.push(c);
                    break;
                case ')': {
                    if (parentheses.isEmpty() || !parentheses.pop().equals('(')) {
                        return false;
                    }
                    break;
                }
                case '}': {
                    if (parentheses.isEmpty() || !parentheses.pop().equals('{')) {
                        return false;
                    }
                    break;
                }
                case ']': {
                    if (parentheses.isEmpty() || !parentheses.pop().equals('[')) {
                        return false;
                    }
                    break;
                }

            }
        }

        return parentheses.isEmpty();
    }
}

Time complexity: O(n)

Space complexity: O(n)

This algorithm guarantees O(n) time complexity due to a single pass through the string, and O(n) space complexity in the worst case, where n is the length of the string, as the stack may store all opening brackets if no closures occur early.