20.Valid_Parentheses_(Easy).md

20. Valid Parentheses (Easy)

Update: Jul 15, 16:03 PM (EST)

Link: https://leetcode.com/problems/valid-parentheses/

Question:

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

Example 2:

Input: s = "()[]{}"

Output: true

Example 3:

Input: s = "(]"

Output: false

Edge cases:

s = "({[]})"
s = "["
s = "]"

KeyPoints:

Follow the hints, put all the opening brackets into the top of the stack, then we check every closing brackets to see it they have the match from stack.pop() (because the requirement has restriction in order).

The Edge cases are tricky, we check if not stack in the else statement for s = "]". Check if len(stack) == 0 for s = "[".

Latest Solution:

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

Time Complexity: $O(n)$, because we loop over s
Space Complexity: $O(n)$, we may need to store all elements in s in the worst case.

My Solution:

Append opening brackets to the stack, then every i that is not opening bracket will be used to match from the top of the stack

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []  # stack is LIFO
        for i in s:                
            if i == '(' or i == '[' or i == '{':
                stack.append(i)
            else:
                # Case when s = ["]"]
                if not stack:
                    return False
                opening = stack.pop()
                if i == ')' and opening != '(':
                    return False
                elif i == ']' and opening != '[':
                    return False
                elif i == '}' and opening != '{':
                    return False
        # If any opening left means there is no matching
        return not stack