Valid Parentheses LeetCode Problem 20 [Python Solution]

In the world of programming, problem-solving is an essential skill, today is for Valid Parentheses LeetCode Problem 20.

This is a classic problem that frequently pops up in coding interviews.

In this blog post, we’ll solve Valid Parentheses, where we are tasked with determining if a given string of parentheses is valid or not.

We’ll explore multiple approaches to solving this problem, analyze their time and space complexities, and understand the constraints involved.

Problem Overview

The problem statement is quite straightforward: given a string s containing only the characters '(', ')', '{', '}', '[', and ']', we need to determine if the input string is valid.

An input string is considered valid if it meets the following criteria:

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

Let’s illustrate this with a few examples:

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Example 1:

Let’s start with a simple example to understand the problem better. We are given the string s = "()".

In this case, we have an open parenthesis '(', followed by a close parenthesis ')'.

According to the rules mentioned earlier, this string is valid because the open and close brackets are in the correct order and match each other.

Understanding the Constraints

Now, before we dive into solving this problem, it’s essential to understand the constraints:

• The length of the input string s is between 1 and 10^4 characters.
• The string s consists of parentheses only, which include '()', '{}', and '[]'.

These constraints give us an idea of the maximum input size we need to handle efficiently.

Valid Parentheses LeetCode Problem Solution

To solve this problem efficiently, we can use a stack data structure and a hash map to keep track of open and close brackets’ relationships.

1. Bruteforce Approach

A naive approach would be to keep removing the valid pairs of brackets iteratively until we can’t find any more matching pairs.

If we end up with an empty string, the input is valid.

However, this approach has a time complexity of O(n^2) in the worst case, as removing a character from the middle of a string requires shifting all subsequent characters.

2. An Efficient Approach with Hash Map

A more efficient approach is to use a stack data structure to keep track of open brackets as we iterate through the string. We also use a hash map to store the relationships between open and close brackets.

Here’s the Python code for this efficient approach:

def isValid(self, s: str) -> bool:
    # Create a hash map to store relationships between brackets.
    bracket_map = {")": "(", "]": "[", "}": "{"}
    stack = []

    for character in s:
        if character not in bracket_map:
            # If it's an open bracket, push it onto the stack.
            stack.append(character)
        else:
            # If it's a close bracket, check if it matches the last open bracket.
            # If not, return False. Otherwise, pop the open bracket from the stack.
            if not stack or stack[-1] != bracket_map[character]:
                return False
            stack.pop()

    # If the stack is empty at the end, all brackets have been matched.
    return not stack

This code uses a stack to keep track of open brackets and checks if each closing bracket matches the last open bracket encountered. If they match, the open bracket is popped from the stack.

Time and Space Complexity

Let’s analyze the time and space complexity of our efficient approach:

• Time Complexity: O(n)
• We iterate through the input string once, performing constant-time operations for each character.
• Space Complexity: O(n)
• The stack can contain at most n/2 brackets, where n is the length of the input string.

Reasoning Behind Our Approach

The reason this approach is efficient is that it allows us to handle large input strings without excessive shifting of characters. We use a stack to keep track of open brackets and a hash map to quickly check if a closing bracket matches the last open bracket.

By using this approach, we ensure that the order of brackets is maintained, and we can efficiently determine the validity of the input string.

Related Interview Questions

• Two Sum LeetCode Problem
• 3Sum LeetCode Problem
• Contains Duplicate LeetCode Problem

Conclusion

In the world of programming, problem-solving skills are highly valued, and the “Valid Parentheses” problem is a classic example that tests your ability to think logically and efficiently.

We explored different approaches to solving this problem, from a brute-force method to an efficient solution using a stack and a hash map.

As a beginner, it’s crucial to understand the problem, consider the constraints, and choose an efficient approach. The efficient approach we discussed not only solves the problem effectively but also handles large input sizes efficiently.

Now, it’s your turn to practice solving this problem and explore more coding challenges.

Solve on LeetCode now.

Feel free to comment, ask questions, make suggestions, and share this content with others.

Happy coding!