Valid Parentheses

easy LeetCode #20

string stack

Description

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
Explanation: The single pair of parentheses is properly matched.

Example 2:
Input: s = "()[]{}"
Output: true
Explanation: All three types of brackets are properly matched in sequence.

Example 3:
Input: s = "(]"
Output: false
Explanation: The opening '(' is closed by ']' which is the wrong type.

Constraints

1 <= s.length <= 10^4
s consists of parentheses only '()[]{}'

Complexity

Show Complexity

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

Hints

Show Hints

Pattern: Stack data structure
Approach: Use a stack. Push opening brackets. For closing brackets, check if stack top matches. Return true if stack is empty at end.
Complexity: Push opening brackets, pop and match for closing brackets

Solutions

Show PY Solution

def solution(s: str) -> bool:
    mappings = {
        "{": "}",
        "[": "]",
        "(": ")",
    }
    reverse_mappings = {
        "}": "{",
        "]": "[",
        ")": "(",
    }

    stack = []

    for c in s:
        if c in list(mappings.keys()):
            stack.append(c)
        else:
            if len(stack) == 0:
                return False
            o = stack.pop()
            if o != reverse_mappings[c]:
                return False

    return len(stack) == 0