Day 4: Valid Parentheses - leetcode - Python3

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: false

SOLUTION:

class Solution:
    def isValid(self, s: str) -> bool:
        dicts: dict={'(':')', '{':'}', '[':']'}
        stack: List[str] = []
        for i in s:
            if i in dicts.keys():
                stack.append(i)
            if i in dicts.values():
               if not stack or dicts[stack.pop()] !=i:#key != value
                   return False
        return not stack #true if stack is empty

Time complexity:
if i in dicts.keys() has a time complexity of $O(1)$
if i in dicts.values() also has a time complexity of $O(1)$
The stack operations stack.append(i), stack.pop(), and not stack are typically constant time operations,the time complexity of the code is dominated by the linear iteration through the input string, resulting in a time complexity of $O(n)$.
Space complexity:
The space complexity of the provided code is $O(n)$, where n is the length of the input string s.
Create a dictionary, dicts, where the opening brackets are keys and the corresponding closing brackets are values.
Initialize an empty stack, stack, to keep track of the opening brackets encountered.
Iterate through each character, i, in the input string, s.
If i is an opening bracket (found in dicts.keys()), push it onto the stack using stack.append(i).
If i is a closing bracket (found in dicts.values()), check if the stack is empty or the top of the stack (stack.pop()) does not match the current closing bracket (dicts[stack.pop()] != i). If either of these conditions is true, return False as the brackets are not balanced.
After processing all characters in s, check if the stack is empty. If it is empty, return True as the brackets are balanced. Otherwise, return False.