Valid Parentheses

The Valid Parentheses problem determines if a string containing only '(', ')', '{', '}', '[' and ']' has correctly matched and ordered brackets. This is efficiently solved using a stack, which naturally handles the Last-In, First-Out (LIFO) requirement for bracket closure.

Why a Stack?

Consider the string `{[()]}`. The inner `()` must close before the outer `[]`, which must close before the outermost `{}`. This nesting behavior means that the most recently opened bracket must be the first one closed. A stack's LIFO property is ideal for tracking open brackets in this order.

How It Works

We iterate through the input string character by character. When an opening bracket ('(', '{', '[') is encountered, it is pushed onto the stack. This remembers its presence and order.

def isValid(s):
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    for char in s:
        if char in mapping:
            top = stack.pop() if stack else '#'
            if mapping[char] != top:
                return False
        else:
            stack.append(char)
    return not stack

Handling Closing Brackets

When a closing bracket (')', '}', ']') is encountered, we perform a crucial check. We look at the top element of the stack. If the stack is empty, it means a closing bracket appeared without a corresponding opening bracket, making the string invalid. If the stack is not empty, we pop its top element. This popped element, which represents the most recently opened bracket, must be the correct matching opening bracket for the current closing bracket. If they do not match, the string is invalid.

Final Check

After iterating through all characters in the string, if the stack is empty, it signifies that every opening bracket found its corresponding closing bracket in the correct order. The string is valid. If the stack is not empty, it means there are unmatched opening brackets, and the string is invalid.

Key takeaways

• A stack is used to track opening brackets in a LIFO manner.
• Opening brackets are pushed onto the stack.
• Closing brackets trigger a pop and a match check against the stack's top element.
• An empty stack at the end indicates all brackets are matched.
• Mismatching brackets or an non-empty stack at the end indicates an invalid string.