LC30.md

Problem: Valid Parentheses

Difficulty: Easy

Description:

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

An input string is valid if:

Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order.

Examples:

Input: s = "()"
Output: true

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

Constraints:

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

Solutions:

To solve this problem we can use the stack data strucutre and keep it always empty for the valid s unless it will be invalid. We mapped each set of parentheses with a unique positive/negative value to check the validity where the valid set should have a sum of zero; i.e 1 + (-1) = 0 for "()" case. The time and space complexity is O(N) where N is the length of s.

def isValid(s):
    """
    :type s: str
    :rtype: bool
    :Time Complexity: O(N)
    :Space Complexity: O(N)
    """
    dct = {"(": 1, ")": -1, "[": 2, "]": -2, "{": 3, "}": -3}
    stack = []

    for char in s:
        val = dct[char]
        if val > 0:
            stack.append(val)
        elif len(stack) > 0 and stack[-1] + val == 0:
            stack.pop()
        else:
            return False

    return True if len(stack) == 0 else False