🅾️20. Valid Parentheses

Easy | Grind 75 | August 11 Thursday, 2022

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 <= 10^4

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

Example 1

Input: s = "()"
Output: true

Example 2

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

Example 3

Input: s = "(]"
Output: false

SOLUTION

Since the strings do not contain any numbers, it makes the problem several factors easier. In the absence of numbers, whenever we see a closing bracket, the preceding character has to be the corresponding open bracket. With just this idea, all the examples above can be solved. However, when the input string is the following: (({{[[]]}})) you need to keep track of which opening brackets have been used/paired. To do this, we will make use of a stack. Whenever we see an open bracket, we will add it to the stack, and whenever we see a closing bracket, we pop the most recent opening bracket off the stack. The idea behind popping the stack when you see a closing bracket is to check if there is a valid corresponding opening bracket. The popping of the stack also means that the current opening bracket has been paired. Once we iterate over all the elements, our stack should be empty for the string to be valid. An empty stack at the end means that we were able to pair every opening bracket with its valid closing bracket.

class Solution:
    def isValid(self, s: str) -> bool:
        # keep track of the opening brackets
        stack = []
        # closing brackets matched to their corresponding opening.
        signs = {")":"(","}":"{","]":"["}
        
        # iterate the string
        for i in s: 
            # if the current character is a closing bracket
            if i in signs: 
                # there is no open brackets to correspond to current closing bracket
                if not stack: 
                    return False
                # if the closing bracket does not correspond to the right open brackets in the stack
                if stack.pop() != signs[i]:
                    return False
                
            # character is an open bracket
            else: 
                stack.append(i) 
        # only valid if the stack is empty. means there are perfect number of pairs. 
        return len(stack) == 0
                

TIME AND SPACE COMPLEXITY

TIME: O(n) where n is the length of the string. We traverse through every character once.

SPACE: O(n) In the worst case, our stack will need n/2 space since we store all the opening brackets. n/2 -> n.