# Valid Parentheses - LeetCode Problem

## Problem Description

Welcome to another fun coding challenge! Today, we'll be tackling the [Valid Parentheses problem](https://leetcode.com/problems/valid-parentheses/).

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:

```python
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.
    

```python
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`.
    

```python
for char in s:
```

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

```python
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.
    

```python
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.
    

```python
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! 😎.