Valid Parentheses

Stack

Problem

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.

Constraints:

• 1 <= s.length <= 104

• s consists of parentheses only '()[]{}'.

For example:

Input: s = "()"
Output: true

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

Input: s = "(]"
Output: false

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

Input: s = "{[]}"
Output: true

Thought Process

• This is a stack problem because we need to check when we come across a closing bracket, if the previous element was an opening bracket. Since stacks can keep track of the last viewed element, a stack is perfect for this scenario.

• We need to use a stack to make sure the previous viewed element is an opening bracket whenever we come across a closing bracket. This is because there always needs to be an opening bracket to a closing bracket.

• We check if brackets are the same type by using a dictionary.

Solution

class Solution:
    def isValid(self, s: str) -> bool:
        
        openBrackets = "({["
        closingBrackets = ")}]"
        matchingBrackets = {")":"(", "]":"[", "}":"{"}
        stack = []
        
        for char in s:
            if char in openBrackets:
                stack.append(char)
            elif char in closingBrackets:
                if not stack: #case2: empty stack but closing brackets
                    return False
                elif matchingBrackets[char] == stack[-1]: #if top of stack is matching bracket
                    stack.pop()
                else: #case 3: mismatching brackets
                    return False
                
        return (stack) == 0
        

Time Complexity

• Time: O(n)

• Space: O(n)