Valid Parentheses - Leetcode Solution

Problem Description:

Given a string 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.

Note that an empty string is also considered valid.

Example: Input: "()[]{}" Output: true

Solution Approach:

This problem can be solved using a stack data structure. We can process the string character by character and push every opening bracket onto the stack. Whenever we encounter a closing bracket, we can check if the top of the stack matches the corresponding opening bracket. If it does, we can pop the opening bracket from the stack. If it doesn't match, we return false since the string is not valid.

At the end, if the stack is empty, it means all brackets are properly terminated, thus our string is valid, otherwise, the string is invalid.

Here is the solution in Python:

class Solution:
    def isValid(self, s: str) -> bool:
        stack = [] # initializing our stack
        brackets = {'(': ')', '{': '}', '[': ']'} # a hash-map to quickly compare opening and closing brackets
        
        for char in s:
            if char in brackets: # if we have a opening bracket, append it to our stack
                stack.append(char)
            elif stack and brackets[stack[-1]] == char: # if we have a closing bracket, check if the top of the stack has a matching opening bracket
                stack.pop()
            else: # if we have a unexpected character
                return False
        
        return not stack # returns true only if the stack is empty

Time and Space complexity:

The time complexity of this algorithm is O(n) since we process each character in the input string once. The space complexity is also O(n) since in a worst-case scenario, we might need to store all the opening brackets in the stack.

1