Leetcode – Valid Parentheses

Spread the love

Balancing symbols, such as parentheses, is a classic problem in computer science that demonstrates the power of simple data structures, like stacks. The problem is not only fundamental to understanding data structures but also frequently appears in coding interviews. LeetCode, a popular platform for interview preparation, features a variation of this problem titled “Valid Parentheses.”

This article will provide an in-depth analysis of the “Valid Parentheses” problem and illustrate how to solve it using Python.

Problem Statement

LeetCode Problem #20: Valid Parentheses

Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid. An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Example

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

The task involves checking whether the input string has balanced parentheses. This includes checking if every opening bracket has a corresponding closing bracket of the same type and if these pairs are correctly ordered.

Understanding the Stack Data Structure

Before diving into the solution, we need to understand the stack data structure. A stack is a linear data structure that follows a particular order in which operations are performed. The order is typically LIFO (Last In First Out), where the last element added is the first one to be removed.

This structure makes stacks ideal for problems involving parentheses, as the most recently opened bracket should be the first one to be closed.

Approach: Using a Stack

We’ll traverse the string one character at a time. As we do, we’ll keep track of the brackets using a stack.

  1. We push each opening bracket we encounter onto the stack.
  2. For every closing bracket, we check the top element of the stack.
    • If the top element is the corresponding opening bracket, we pop it off the stack.
    • If it’s not, the brackets are not balanced, so we return False.
  3. If the stack is empty after this process, the string is balanced, and we return True. If not, some opening brackets were not closed, so we return False.

Here’s a Python function implementing this approach:

def isValid(s: str) -> bool:
    bracket_map = {"(": ")", "[": "]", "{": "}"}
    open_brackets = set(["(", "[", "{"])
    stack = []
    for i in s:
        if i in open_brackets:
            stack.append(i)
        elif stack and i == bracket_map[stack[-1]]:
            stack.pop()
        else:
            return False
    return stack == []

In this function, bracket_map maps each opening bracket to its corresponding closing bracket. open_brackets is a set of all opening brackets, used for quickly checking if a character is an opening bracket. We then initialize an empty stack.

We iterate over the input string. For each character:

  • If it’s an opening bracket, we push it onto the stack.
  • If it’s a closing bracket, we check the top of the stack. If the stack isn’t empty and the character is the closing bracket for the top of the stack, we pop the stack. If not, we return False because the brackets aren’t balanced.
  • After checking all the characters, if the stack is empty, we return True, indicating that the brackets are balanced. If not, some opening brackets weren’t closed, so we return False.

The time complexity of this solution is O(n), where n is the length of the string. This is because we simply iterate over the string once.

Conclusion

The “Valid Parentheses” problem is an excellent exercise in understanding and utilizing the stack data structure. This data structure, due to its LIFO nature, provides an elegant and efficient solution to the problem.

The Python solution presented in this article demonstrates how to use a stack to keep track of opening and closing brackets. It also illustrates how to use a dictionary and a set for fast lookups, an essential technique when dealing with large inputs.

Leave a Reply