Leetcode Day 5: Valid Parentheses Explained

The problem is as follows:
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Here is how I solved it:
This is a good example on when to use a stack data structure. We are going to use a stack to keep track of the open brackets and ensure they are closed correctly and in the right order. Let's first figure out what is a stack. Look at this image:

A stack is a Last-In-First-Out (LIFO) data structure, meaning the last element added (pushed) to the stack is the first one to be removed (popped). This makes it ideal for matching parentheses, as we need to ensure that the most recent open bracket is closed by the corresponding close bracket.

Let's step through the logic.

class Solution:
    def isValid(self, s: str) -> bool:
        // my solution here

• Create an empty stack to keep track of open brackets.
• Create a dictionary to map each type of open bracket to its corresponding close bracket.

stack = []
mapping_parentheses = {"(" : ")", "[" : "]", "{" : "}"}

• Loop through each character in the string s.

• If the character is an open bracket (i.e., it is a key in the mapping_parentheses dictionary), "push" it onto the stack.

• Else if the character is a close bracket, check two conditions:

1. not stack: If the stack is empty, it means there is no corresponding open bracket for the close bracket, so return False.
2. char != mapping_parentheses[stack.pop()]: Pop the top element from the stack and check if the popped element matches the current close bracket using the dictionary. If not, return False.

for char in s: 
    if char in mapping_parentheses: 
        stack.append(char)
    elif not stack or char != mapping_parentheses[stack.pop()]:
        return False

• After processing all characters, if the stack is empty, it means all open brackets were correctly matched and closed. If the stack is not empty, it means there are unmatched open brackets, so return False.

return not stack

Here is the completed solution:

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        mapping_parentheses = {"(" : ")", "[" : "]", "{" : "}"}

        for char in s: 
            if char in mapping_parentheses: 
                stack.append(char)
            elif not stack or char != mapping_parentheses[stack.pop()]:
                return False
        return not stack