Valid Parentheses in Python with O(n) Time Complexity

Input: s = "()"
Output: true

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

Input: s = "(]"
Output: false

Input: s = "([)]"
Output: false

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

Understanding the Problem

The core challenge of this problem is to ensure that every opening bracket has a corresponding closing bracket and that they are correctly nested. This problem is significant in various applications such as parsing expressions in compilers, validating mathematical expressions, and ensuring the correctness of nested structures in programming languages.

Potential pitfalls include mismatched brackets, incorrect nesting, and unbalanced brackets.

Approach

To solve this problem, we can use a stack data structure. The stack helps us keep track of the opening brackets encountered, and we can match them with the closing brackets as we traverse the string.

Naive Solution

A naive solution might involve checking each pair of brackets, but this would be inefficient and complex to implement. This approach is not optimal due to its high time complexity.

Optimized Solution

The optimized solution involves using a stack to keep track of the opening brackets. As we traverse the string, we push each opening bracket onto the stack. When we encounter a closing bracket, we check if it matches the top of the stack. If it does, we pop the stack; otherwise, the string is invalid.

Algorithm

1. Initialize an empty stack.
2. Create a mapping of closing brackets to their corresponding opening brackets.
3. Traverse the string character by character.
4. If the character is an opening bracket, push it onto the stack.
5. If the character is a closing bracket, check if the stack is empty or if the top of the stack does not match the corresponding opening bracket. If either condition is true, return false.
6. If the stack is empty at the end of the traversal, return true; otherwise, return false.

Code Implementation

def isValid(s: str) -> bool:
    # Dictionary to hold the mappings of closing to opening brackets
    bracket_map = {')': '(', '}': '{', ']': '['}
    # Stack to keep track of opening brackets
    stack = []

    # Traverse each character in the string
    for char in s:
        # If the character is a closing bracket
        if char in bracket_map:
            # Pop the top element from the stack if it's not empty, otherwise assign a dummy value
            top_element = stack.pop() if stack else '#'
            # Check if the popped element matches the corresponding opening bracket
            if bracket_map[char] != top_element:
                return False
        else:
            # If it's an opening bracket, push it onto the stack
            stack.append(char)

    # If the stack is empty, all brackets were matched correctly
    return not stack

Complexity Analysis

The time complexity of this solution is O(n) because we traverse the string once. The space complexity is also O(n) due to the stack used to store opening brackets.

Edge Cases

Consider the following edge cases:

• Empty string: Should return true.
• Single type of bracket: "((()))" should return true, "((())" should return false.
• Mixed types of brackets: "{[()]}" should return true, "{[(])}" should return false.

Testing

To test the solution comprehensively, consider the following test cases:

assert isValid("()") == True
assert isValid("()[]{}") == True
assert isValid("(]") == False
assert isValid("([)]") == False
assert isValid("{[]}") == True
assert isValid("") == True
assert isValid("(((((((())))))))") == True
assert isValid("(((((((()))))))") == False

Thinking and Problem-Solving Tips

When approaching such problems, consider using data structures like stacks that can help manage nested structures. Practice similar problems to develop a deeper understanding of stack operations and their applications.

Conclusion

Understanding and solving the "Valid Parentheses" problem is crucial for mastering stack-based algorithms. This problem is a common interview question and has practical applications in parsing and validating nested structures.

Additional Resources

• LeetCode - Valid Parentheses
• GeeksforGeeks - Check for Balanced Parentheses
• Coursera - Data Structures