Are Your Parentheses Balanced?

Validating parentheses is a common question that tech interviewers like to ask, primarily because it tests your understanding of data structures and algorithms. The challenge usually revolves around determining if a string consisting of parentheses is valid, meaning every opening parenthesis has a corresponding closing parenthesis, and they are correctly nested. This problem can be tackled efficiently using a stack data structure.

Understanding the Problem

A string is considered valid if:

1. Every opening bracket ( has a corresponding closing bracket ).
2. These brackets must close in the right order. For instance, ((())) is valid, but (() and ())( are not.

Why Use a Stack?

A stack perfectly fits this problem because it follows the Last In First Out (LIFO) principle, allowing you to manage the opening brackets efficiently. Whenever an opening bracket is encountered, it gets pushed onto the stack. When a closing bracket is found, you check if there is a corresponding opening bracket on the top of the stack.

Code Implementation

Let's take a look at how we can implement this logic in Python. Below is a straightforward example of how to check for valid parentheses:

1def is_valid_parentheses(s):
2    stack = []
3    # Map closing brackets to their corresponding opening brackets
4    bracket_map = {')': '(', '}': '{', ']': '['}
5    
6    # Iterate through each character in the string
7    for char in s:
8        # If the character is a closing bracket
9        if char in bracket_map:
10            # Pop the top element if the stack is not empty, else assign a dummy value
11            top_element = stack.pop() if stack else '#'
12            # Check for a match, if not return False
13            if bracket_map[char] != top_element:
14                return False
15        else:
16            # It's an opening bracket, push it onto the stack
17            stack.append(char)
18    
19    # If the stack is empty, all the brackets are valid
20    return not stack
21
22# Example usage
23print(is_valid_parentheses("()"))        # True
24print(is_valid_parentheses("()[]{}"))    # True
25print(is_valid_parentheses("(]"))        # False
26print(is_valid_parentheses("([)]"))      # False
27print(is_valid_parentheses("{[]}"))      # True

Explanation of the Code

1. Stack Initialization: An empty list is created to serve as our stack.

2. Bracket Mapping: A dictionary maps closing brackets to their respective opening brackets for easy look-up.

3. Iterating Through Characters: The for loop processes each character in the string. If it encounters a closing bracket, it checks whether the most recent opening bracket (if any) matches it. If they don't match, the function immediately returns False.

4. Adding to the Stack: If an opening bracket is found, it gets added to the stack.

5. Final Check: Once all characters are processed, if the stack is empty, that means all opening brackets were matched with closing brackets, and the string is valid.

Time Complexity

The time complexity of this solution is O(n), where n is the length of the string. Each character is processed once, making this approach efficient for large inputs. The space complexity is also O(n) in the worst case, when all characters are opening brackets.