Valid Parentheses — Day 7(Python)

Photo by Nathan Dumlao on Unsplash

Today we will be looking into one of Leetcode’s Easy tagged questions. Let us jump into the problem without losing much time.

20. Valid Parentheses

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.

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Example 4:

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

Example 5:

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

Constraints:

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

Solution

Since we have a limited set of brackets to worry about in this problem, we can use a dictionary that holds the key as closing brackets and value as a respective opening bracket. We need a stack which will hold the order of opening brackets, we can remove the opening brackets from the stack when we find the right closing bracket.

1. Construct a dictionary that holds opening brackets (value) and closing brackets(key).
2. Have a set of opening brackets. A set will help us to identify opening brackets.
3. Run the loop for each character in the string, check if it is an opening bracket. If yes, push it into the stack.
4. If the current character is a closing bracket, check if the topmost element in the stack is the right opening bracket for the current closing bracket. If yes, pop the topmost element in the stack.
5. If any of the above condition is False, return False
6. Once the entire loop is completed, check for any remaining items in the stack. If the stack is empty return true, else return false.

class Solution:
    def isValid(self, s: str) -> bool:
        dictionary_brackets = {'}':'{',')':'(', ']':'['}
        open_bracket = ('{','(','[')
        stack_bracket = []
        for each_char in s:
            if stack_bracket == [] or each_char in open_bracket:
                stack_bracket.append(each_char)
            elif(dictionary_brackets[each_char]==stack_bracket[-1]):
                stack_bracket.pop()
            else:
                return False
        return False if stack_bracket else True

Complexity analysis

Time Complexity

We would be required to traverse through each character in the string which would take O(N).

Space Complexity

In worst-case-scenario, if our input string is ‘(((([[[[[{{{{’. The entire string will be stored in the stack, which means the space complexity will be O(N).

I would like to improve my writing skills so any suggestions or critiques are highly welcomed.