Valid Parentheses

Problem: Valid Parentheses

Clarify the problem

The "Valid Parentheses" problem asks you to determine if a given string containing only parentheses ('(', ')', '{', '}', '[', ']') is valid. The string is considered valid if all the opening parentheses are properly closed.

Analyze the problem

We need to check if the given string has a valid arrangement of parentheses. For a string to be valid, the opening and closing parentheses must be balanced and nested correctly. Additionally, the order of parentheses must be maintained.

Design an algorithm

One approach to solving this problem is by using a stack. We can iterate through the string, and for each character, if it is an opening parenthesis, we push it onto the stack. If it is a closing parenthesis, we check if it matches the top element of the stack. If they match, we pop the top element from the stack. If they don't match or the stack is empty, the string is invalid. Finally, after iterating through the entire string, if the stack is empty, the string is valid.

Explain the approach

We will iterate through the string character by character. If an opening parenthesis is encountered, we will push it onto the stack. If a closing parenthesis is encountered, we will check if it matches the top element of the stack. If they match, we will pop the top element from the stack. If they don't match or the stack is empty, the string is invalid. After iterating through the entire string, if the stack is empty, the string is valid.

Write clean and readable code


def isValid(s):
    stack = []
    opening_parentheses = {'(', '{', '['}
    closing_parentheses = {')', '}', ']'}
    parentheses_map = {'(': ')', '{': '}', '[': ']'}
    
    for char in s:
        if char in opening_parentheses:
            stack.append(char)
        elif char in closing_parentheses:
            if not stack or parentheses_map[stack.pop()] != char:
                return False
    
    return not stack


def main():
    test_cases = [
        "()",  # Expected output: True
        "()[]{}",  # Expected output: True
        "(]",  # Expected output: False
        "([)]",  # Expected output: False
        "{[]}"  # Expected output: True
    ]
    
    for s in test_cases:
        result = isValid(s)
        print(f"String: {s}  Valid: {result}")


if __name__ == '__main__':
    main()

Test the code

We will test the code with different test cases, including valid and invalid strings.

Optimize if necessary

The given solution has a time complexity of O(n) since we iterate through the string once. This is already an optimal solution for the "Valid Parentheses" problem.

Handle error cases

The code currently assumes that the input string only contains parentheses characters. It may not handle cases where the string contains other characters. Additional checks can be added to handle such cases if needed.

Discuss complexity analysis

The time complexity of the solution is O(n) since we iterate through the string once. The space complexity is O(n) in the worst-case scenario when all opening parentheses are pushed onto the stack.

Python