Solving the Parentheses Validity Problem: Naive vs. Efficient Approaches in JavaScript

Introduction

The Parentheses Validity Problem is a common coding challenge where you’re tasked with determining if the parentheses in a given string are correctly paired and closed. In this blog post, we’ll explore two different approaches to tackle this problem: the naive approach and an efficient one.

Problem Statement

Given a string containing only three types of characters: ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, we need to determine if the input string is valid. To be valid, the string must have parentheses opened and closed in the correct order.

Example

Let’s illustrate the problem with an example:

const str = "{[()]}";
// The solution should return true because the string has valid parentheses.

const invalidStr = "([)]";
// The solution should return false because the string has incorrectly paired parentheses.

Naive Approach

The naive approach to solving the Parentheses Validity Problem involves using a stack data structure and explicit character checks.

Algorithm

const naiveApproach = (s) => {
  let stack = [];

  for (let i = 0; i < s.length; i++) {
    if (s.charAt(i) == '[' || s.charAt(i) == '(' || s.charAt(i) == '{') {
      stack.push(s.charAt(i));
    } else if (
      stack[stack.length - 1] == '[' && s.charAt(i) == ']' ||
      stack[stack.length - 1] == '(' && s.charAt(i) == ')' ||
      stack[stack.length - 1] == '{' && s.charAt(i) == '}'
    ) {
      stack.pop();
    } else {
      stack.push(s.charAt(i));
    }
  }

  if (stack.length === 0) return true;
  return false;
};

Algorithm

Here’s a step-by-step breakdown of the naive approach:

1. Create an empty stack.
2. Loop through each character in the input string.
3. If the character is an opening parenthesis (‘[‘, ‘(‘, or ‘{‘), push it onto the stack.
4. If the character is a closing parenthesis (‘]’, ‘)’, or ‘}’):
   • Check if it matches the corresponding opening parenthesis at the top of the stack.
   • If they match, pop the opening parenthesis from the stack.
   • If they don’t match, push the closing parenthesis onto the stack.
5. After processing all characters, check if the stack is empty.

Complexity

The naive approach has a time complexity of O(n), where ‘n’ is the length of the input string. However, it uses multiple conditional statements, which can make the code less elegant and efficient.

Efficient Approach

The efficient approach to solving the Parentheses Validity Problem is a more elegant solution that uses a mapping of opening and closing parentheses.

const efficientApproach = (s) => {
  let parenthesesMatch = {
    '{': '}',
    '[': ']',
    '(': ')',
  };
  let stack = [];

  for (let char of s) {
    if (parenthesesMatch[char]) {
      stack.push(char);
    } else {
      let top = stack.pop();
      if (char !== parenthesesMatch[top]) {
        return false;
      }
    }
  }

  return stack.length === 0;
};

Algorithm

Here’s a step-by-step breakdown of the efficient approach:

1. Create a parenthesesMatch object that maps opening and closing parentheses characters.
2. Create an empty stack.
3. Loop through each character in the input string.
4. If the character is an opening parenthesis, push it onto the stack.
5. If the character is a closing parenthesis:
   • Check if it matches the corresponding opening parenthesis at the top of the stack using the parenthesesMatch object.
   • If they match, pop the opening parenthesis from the stack.
   • If they don’t match, return false.
6. After processing all characters, check if the stack is empty.

Complexity

The efficient approach also has a time complexity of O(n), making it a more optimal and concise solution. It improves code readability and maintainability.

Wrapping Up

In this blog post, we explored two different approaches to solving the Parentheses Validity Problem in JavaScript. The naive approach, while effective, uses multiple conditional statements, which can make the code less elegant and efficient. In contrast, the efficient approach, which uses a mapping of opening and closing parentheses, is recommended for its simplicity and performance.

Solving coding problems efficiently is crucial in coding interviews and competitive programming. The efficient approach presented here demonstrates how you can optimize your code and achieve cleaner, more scalable solutions. Remember that the choice of approach depends on the specific context and requirements of your coding task.

Happy coding!