Valid Parentheses - Python Solution

1. Introduction

"Valid Parentheses" is a classic problem in the domain of string processing and stack data structures. The challenge is to check if a given string containing various types of brackets is valid in terms of the opening and closing order. This problem is commonly used to assess understanding of basic data structures and string manipulation.

Problem

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. A string is considered valid if all open brackets are closed by the same type of brackets and in the correct order. Each closing bracket must have a corresponding opening bracket of the same type.

2. Solution Steps

1. Initialize an empty stack to keep track of opening brackets.

2. Iterate through each character in the string.

3. If the character is an opening bracket, push it onto the stack.

4. If it's a closing bracket, check if it matches the top element of the stack. If it matches, pop the top element; otherwise, the string is invalid.

5. After processing all characters, if the stack is empty, the string is valid; otherwise, it's invalid.

6. Return true if the string is valid, otherwise false.

3. Code Program

def isValid(s):
    stack = []
    mapping = {")": "(", "}": "{", "]": "["}

    for char in s:
        if char in mapping:
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return False
        else:
            stack.append(char)

    return not stack

# Example Usage
print(isValid("()"))       # Output: true
print(isValid("()[]{}"))   # Output: true
print(isValid("(]"))       # Output: false

Output:

true
true
false

Explanation:

1. Stack Utilization: A stack is used to keep track of the opening brackets encountered.

2. Matching Brackets: For each closing bracket, the stack is checked for the corresponding opening bracket.

3. Validity Check: If at any point the closing bracket doesn't match the top of the stack, the string is invalid.

4. Final Stack State: If the stack is empty at the end of the iteration, all brackets were properly closed and matched.

5. Efficient Solution: The solution runs in O(n) time complexity, where n is the length of the string.

6. Edge Cases Handling: Handles cases with unbalanced brackets and empty stack scenarios.