Problem Description

Welcome to another fun coding challenge! Today, we'll be tackling the Valid Parentheses problem.

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.

That's it! Now, let's dive into the solution.

Solution

First, we'll start by initializing an empty stack. Then, we'll iterate through each character in the input string. If the current character is an opening bracket, we'll push it onto the stack. If the current character is a closing bracket, we'll check if the stack is empty. If it is, then the input string is invalid. Otherwise, we'll pop the top character from the stack and check if it matches the closing bracket. If it doesn't match, then the input string is invalid. Finally, we'll check if the stack is empty. If it is, then the input string is valid. Otherwise, it's invalid.

Here's the Python code for our solution:

def isValid(s: str) -> bool:
    stack = []
    brackets = {')': '(', '}': '{', ']': '['}

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

    return not stack

Let's go through this code step-by-step.

1. We start by initializing an empty stack and a dictionary of bracket pairs.

stack = []
brackets = {')': '(', '}': '{', ']': '['}

The dictionary brackets maps each closing bracket to its corresponding opening bracket. For example, ')' maps to '(', '}' maps to '{', and ']' maps to '['.

1. We iterate through each character in the input string s.

for char in s:

1. If the current character is an opening bracket, we'll push it onto the stack.

if char in brackets.values():
    stack.append(char)

1. If the current character is a closing bracket, we'll check if the stack is empty. If it is, then the input string is invalid.

elif char in brackets.keys():
    if not stack or brackets[char] != stack.pop():
        return False

The if not stack condition checks if the stack is empty. If it is, then we know that there's no matching opening bracket for the current closing bracket, so the input string is invalid. The brackets[char] != stack.pop() condition checks if the top of the stack contains the corresponding opening bracket for the current closing bracket. If it doesn't match, then the input string is invalid.

1. Finally, we'll check if the stack is empty. If it is, then the input string is valid. Otherwise, it's invalid.

return not stack

The not stack expression returns True if the stack is empty, and False if it's not empty. Since we're checking for validity, we want to return True if the stack is empty (i.e., all brackets have been matched), and False if it's not empty (i.e., there are unmatched opening brackets).

Complexity Analysis

Now that we have our solution, let's analyze its time and space complexity.

Time Complexity

Our solution iterates through each character in the input string. Since we're doing constant time operations for each character (pushing and popping from a stack, and checking if a key is in a dictionary), the time complexity of our solution is O(n), where n is the length of the input string.

Space Complexity

Our solution uses a stack to keep track of the opening brackets. The maximum size of the stack is n/2, where n is the length of the input string. This happens when the input string consists entirely of opening brackets, followed by their corresponding closing brackets. Therefore, the space complexity of our solution is also O(n).

Conclusion

And there you have it! We've successfully tackled the Valid Parentheses problem. I hope you found this blog post helpful and informative. Remember, practice makes progress. Happy Coding! 😎.