Valid Parentheses

You are given a string s consisting of the following characters: '(', ')', '{', '}', '[' and ']'.

The input string s is valid if and only if:

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

Return true if s is a valid string, and false otherwise.

The brackets are not closed in the correct order.

Approach

Use a stack to track open brackets. When we see an opening bracket, push it. When we see a closing bracket, the top of the stack must be the matching opening bracket; otherwise the string is invalid. At the end, the stack must be empty. This correctly handles the empty string case.

Why It Works

The stack represents the order of unclosed opening brackets. A closing bracket must match the most recent opening bracket to preserve correct nesting. Any mismatch or leftover opening brackets means the string is invalid; if every close matches and the stack is empty, the string is valid.

Complexity

• Time: O(n)
• Space: O(n)

Reference Implementation (Python)

class Solution:
    def isValid(self, s: str) -> bool:
        pairs = {')': '(', ']': '[', '}': '{'}
        stack = []
        for ch in s:
            if ch in pairs:
                if not stack or stack.pop() != pairs[ch]:
                    return False
            else:
                stack.append(ch)
        return len(stack) == 0