LeetCode 20 Solution: Valid Parentheses in Python

In this blog post, we will explore an efficient solution for one of the most commonly asked coding interview questions: LeetCode 20: Valid Parentheses. This problem tests your ability to determine if a string containing only parentheses, such as (), {}, and [], is valid. The goal is to ensure that the parentheses are properly balanced and nested.

Understanding how to solve this problem will not only help you on coding platforms like LeetCode, but it will also strengthen your grasp of important data structures like stacks, which are often used in algorithms involving paired or nested elements.

Problem Statement: What is “Valid Parentheses”?

The task in is to check whether a given string is valid based on the following rules:

1. Every opening bracket must have a corresponding closing bracket of the same type.
2. The brackets must close in the correct order.

For example:

• s = "()" is valid because it is a correctly balanced pair.
• s = "()[]{}" is valid because each type of bracket is opened and closed in the correct order.
• s = "(]" is not valid because the closing ] does not match the opening (.

How to Approach the Valid Parentheses Problem

One of the best ways to solve this problem is by using a stack data structure. A stack works perfectly for this problem because it follows a “Last In, First Out” approach. This means that when you encounter a closing bracket, you can check if it matches the most recently opened bracket.

Here is a simple approach:

1. Iterate over the string character by character.
2. If you find an opening bracket (like (, {, [), push it onto the stack.
3. When you find a closing bracket (like ), }, ]), check the top of the stack to see if it matches the corresponding opening bracket.
4. If it does, pop the opening bracket from the stack. If it doesn’t, or if the stack is empty, the string is invalid.
5. Finally, after processing all the characters, if the stack is empty, the string is valid; otherwise, it is not.

Python Solution for Valid Parentheses

Now, let’s take a look at the LeetCode 20 solution in Python:

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

    for char in s:
        # If it's an opening bracket, push it to the stack
        if char in matching_bracket.values():
            stack.append(char)
        
        # If it's a closing bracket, check the top of the stack
        elif char in matching_bracket:
            if not stack or stack.pop() != matching_bracket[char]:
                return False

    return not stack

Explanation of the Code:

• We start by initializing an empty stack, which will store the opening brackets as we process them.
• A dictionary called matching_bracket is used to map each closing bracket to its corresponding opening bracket.
• As we loop through the string, for every opening bracket ((, {, [), we push it onto the stack.
• For every closing bracket (), }, ]), we check if the stack is empty or if the top of the stack doesn’t match the corresponding opening bracket. If so, we return false because the string is not valid.
• After processing all the characters, if the stack is empty, it means all brackets were matched correctly, and we return true.

Why Use a Stack for Valid Parentheses?

The reason we use a stack is that it allows us to efficiently keep track of the most recently opened bracket. As we process each character in the string, the stack helps us ensure that every opening bracket has a corresponding closing bracket in the correct order. This method is both simple and fast, making it perfect for handling even large input sizes.

Edge Cases to Consider

When solving the “valid parentheses” problem, it’s important to consider several special cases:

• Empty string: If the input string is empty (""), the function should return true because there are no unmatched brackets.
• Mismatched brackets: For input like "(]" or "([)]", the function should return false because the brackets are not properly nested or ordered.
• Unbalanced brackets: If there are too many opening brackets (like "((()))((("), the function should return false because not all opening brackets are matched with closing ones.

Time and Space Complexity

This solution is efficient with a time complexity of O(n), where n is the length of the input string. We process each character in the string exactly once, and both pushing and popping elements from the stack happen in constant time.

The space complexity is also O(n) in the worst case, where all the opening brackets need to be stored in the stack before they are matched.

Final Thoughts on the LeetCode 20 Solution

The “Valid Parentheses” problem on LeetCode is a great example of how a stack can be used to solve problems involving nested or paired elements. This LeetCode 20 solution is efficient, easy to understand, and handles all types of valid and invalid input strings.

By understanding how to implement this algorithm, you not only solve this problem but also gain insight into how to approach similar problems that involve balancing or matching pairs, such as HTML tag validation or evaluating mathematical expressions.

Mastering this pattern will help you in many coding challenges and is a must-know for technical interviews. Keep practicing, and soon problems like this will become second nature!

Happy Coding!

---

Looking for more LeetCode solutions? Stay tuned for upcoming guides on tackling other LeetCode challenges in Python. Whether you’re preparing for technical interviews or aiming to improve your coding skills, exploring a variety of problems will enhance your understanding and proficiency.

You can find this problem on LeedCode, click here.