20. Valid Parentheses#

Difficulty: Easy

Link to Problem: To see the Valid Parentheses problem on LeetCode, click here!

Given a string s 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.

  3. Every close bracket has a corresponding open bracket of the same type.

Constraints:

  • 1 <= s.length <= \(10^4\)

  • s consists of parentheses only '()[]{}'.

def isValid(s):
    # Create an empty stack to store opening brackets
    stack = []
    
    # Define a mapping for matching brackets
    bracket_mapping = {')': '(', '}': '{', ']': '['}
    
    # Iterate through the characters in the input string
    for char in s:
        # If the character is an opening bracket, push it onto the stack
        if char in bracket_mapping.values():
            stack.append(char)
        # If the character is a closing bracket
        elif char in bracket_mapping.keys():
            # Pop the top element from the stack if it exists, or use a dummy value '#'
            top_element = stack.pop() if stack else '#'
            # If the popped element does not match the corresponding opening bracket, return False
            if bracket_mapping[char] != top_element:
                return False
        # If the character is not a bracket, ignore it
        
    # After processing the entire string, if there are any unmatched opening brackets left in the stack, return False
    return len(stack) == 0

Explanation:#

  1. We start by defining the isValid function that takes a single argument s, which is the input string containing parentheses and brackets.

  2. Inside the function, we create an empty stack, which is a list in Python, to store opening brackets as we encounter them in the input string. The stack will help us keep track of the brackets and their order.

  3. We define a bracket_mapping dictionary that maps each closing bracket to its corresponding opening bracket. This mapping will be used to check if a closing bracket matches the most recent opening bracket in the stack.

  4. We iterate through each character char in the input string s using a for loop.

  5. If the character char is an opening bracket (i.e., it exists in the values() of bracket_mapping), we push it onto the stack using the append() method.

  6. If the character char is a closing bracket (i.e., it exists in the keys() of bracket_mapping), we need to check if it matches the corresponding opening bracket. To do this, we pop the top element from the stack (if it exists) and store it in top_element. We use a dummy value '#' if the stack is empty to avoid errors.

  7. We then compare top_element with the corresponding opening bracket using bracket_mapping[char]. If they do not match, it means the string is not valid, and we return False.

  8. If the character char is not a bracket, we simply ignore it and continue the loop.

  9. After processing the entire string, we check if there are any unmatched opening brackets left in the stack. If the stack is empty, it means all opening brackets have been properly matched and closed, and we return True. Otherwise, we return False.

  10. Finally, we provide some test cases at the bottom of the code to demonstrate how the function works for different input strings.

Test cases#

# Example 1:
print(isValid("()"))    

True

# Example 2:
print(isValid("()[]{}")) 

True

# Example 3:
print(isValid("(]"))     

False

Let’s analyze the time and space complexity of the isValid function:

Time Complexity:

  • The function iterates through each character in the input string s once, performing constant-time operations for each character.

  • Pushing and popping elements from the stack (list) also takes constant time in most cases.

  • Therefore, the overall time complexity of the function is \(O(n)\), where \(n\) is the length of the input string s.

Space Complexity:

  • The space complexity of the function is determined by the space used by the stack and the bracket_mapping dictionary.

  • In the worst case, if the input string s consists entirely of opening brackets, the stack can potentially contain all of these opening brackets, resulting in a space complexity of \(O(n)\) in terms of the stack.

  • The bracket_mapping dictionary has a constant number of key-value pairs (3 pairs in this case).

  • Therefore, the overall space complexity of the function is \(O(n)\), where \(n\) is the length of the input string s, mainly due to the stack space.

In summary:

  • The time complexity is \(O(n)\) because we iterate through the string once.

  • The space complexity is \(O(n)\) due to the stack used to keep track of opening brackets.

Challenging Exercises:#

  1. Valid Expressions: Modify the problem to validate not only brackets but also arithmetic expressions containing parentheses, such as “\(2 * (3 + 5) / (4 - 2)\)”.

  2. Valid Parentheses Combinations: Write a function to generate all valid combinations of n pairs of parentheses, where \(n\) is a positive integer. For example, for \(n = 3\), the valid combinations are [“((()))”, “(()())”, “(())()”, “()(())”, “()()()”].