Valid Parentheses

Easy Subject: Stack

Time Complexity

O(N)

Space Complexity

O(N)

Problem Description

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if brackets close in the correct order and with matching types.

Optimal Solution

Python

def isValid(s):
    stack = []
    mapping = {")": "(", "}": "{", "]": "["}
    for char in s:
        if char in mapping:
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return False
        else:
            stack.append(char)
    return not stack