How to Solve the Valid Parentheses-Leetcode

When it comes to coding interviews, the problem of validating parentheses is a classic and fundamental problem that appears frequently. It tests your understanding of data structures, particularly stacks, and your ability to apply them in real-world scenarios.

In this blog post, we’ll dive deep into the “Valid Parentheses” problem, explore different approaches to solve it, and discuss the time and space complexities involved. By the end of this article, you’ll have a solid understanding of the problem and be well-prepared to tackle similar challenges.

Problem Statement

Valid Parentheses: Given a string containing just the characters '(', ')', '{', '}', '[', and ']', determine if the input string is valid.

An input string is considered valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding earlier open bracket of the same type.

Example:

• Input: "()" Output: true

• Input: "()[]{}" Output: true

• Input: "(]" Output: false

• Input: "([)]" Output: false

• Input: "{[]}" Output: true

Approach

The problem can be solved efficiently using a stack data structure. Stacks follow the Last-In-First-Out (LIFO) principle, making them perfect for problems involving nested structures and backtracking, such as validating balanced parentheses.

Step-by-Step Solution

1. Use a Stack to Track Opening Brackets: As we traverse through the string, every time we encounter an opening bracket ('(', '{', '['), we push it onto the stack.

2. Check for Matching Closing Brackets: When we encounter a closing bracket (')', '}', ']'), we check if the stack is not empty and whether the top element of the stack matches the corresponding opening bracket. If it does, we pop the stack; otherwise, the string is invalid.

3. Stack Should Be Empty at the End: After processing the entire string, if the stack is empty, it means every opening bracket had a matching closing bracket in the correct order, and the string is valid.

Example

Let’s walk through an example with the input string "{[()]}()".

• Input: "{[()]()}"
• Stack at each step:

Step	Character	Action	Stack
1	{	Push to stack	{
2	[	Push to stack	{[
3	(	Push to stack	{[(
4	)	Pop and match with (	{[
5	]	Pop and match with [	{
6	}	Pop and match with {	[]
7	(	Push to stack	(
8	)	Pop and match with (	[]

• Output: true (The string is valid).

JavaScript Implementation

function isValid(s) {
  // Stack to store opening brackets
  const stack = [];
  
  // Mapping of closing to opening brackets
  const mapping = {
    ')': '(',
    '}': '{',
    ']': '['
  };

  // Iterate through each character in the string
  for (const char of s) {
    // If the character is a closing bracket
    if (mapping[char]) {
      // Pop the top element of the stack; if the stack is empty, set it to '#'
      const topElement = stack.length > 0 ? stack.pop() : '#';

      // If the mapping for the closing bracket doesn't match the top element
      if (topElement !== mapping[char]) {
        return false;
      }
    } else {
      // If it is an opening bracket, push it onto the stack
      stack.push(char);
    }
  }

  // If the stack is empty, all the brackets were properly closed
  return stack.length === 0;
}