20. Valid Parentheses

Problem Description

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', 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. 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

My Idea

The idea here is to use a list as a stack, taking advantage of the LIFO strategy. Every time we see an opening bracket we add it to the stack and when we see a closing one, we pop the last added one(the last opening bracket) and check if it matches the closing one (the current one).

My solution

# Time Complexity: O(n)
def isValid( s: str) -> bool:
    stack=[]
    for c in s:
        if c in "({[":
            stack.append(c)
        else:
            if stack==[]:
                return False
            c2=stack.pop()
            if (c2=='(' and c!=')')
            or (c2=="[" and c!="]")
            or (c2=="{" and c!="}"):
                return False
    if stack==[]:
        return True
    return False

20. Valid Parentheses - LeetCode