Valid Parenthesis Checker

The Valid Parenthesis Checker is a most asked question in the realm of Data Structures and Algorithms (DSA), it was asked to me personally in few of the interviews.

Problem Statement

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

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

Examples:

Input: "()"
Output: true
Explanation: Brackets are well formed, so we need to return true

Input: "()[]{}"
Output: true
Explanation: Brackets are well formed, so we need to return true

Input: "(]"
Output: false
Explanation: Opening and closing brackets are not same, so return false

Approach

To solve this problem, we can use a stack data structure. The idea is to traverse the string and use the stack to keep track of the opening brackets. When we encounter a closing bracket, we check if it matches the most recent opening bracket (which should be at the top of the stack). If it matches, we pop the top of the stack. Otherwise, the string is not valid.

Step-by-Step Solution

1. Initialize a Stack:
   • Use an array to simulate the stack.
2. Create a Map for Matching Brackets:
   • Use a hash map to store the pairs of matching brackets.
3. Traverse the String:
   • For each character in the string:
     • If it is an opening bracket, push it onto the stack.
     • If it is a closing bracket, check if the stack is not empty and the top of the stack matches the corresponding opening bracket. If so, pop the stack; otherwise, return false.
4. Check the Stack:
   • After processing all characters, the stack should be empty for the string to be valid.

Implementation in JavaScript

Here’s how you can implement the Valid Parenthesis Checker in JavaScript:

function isValid(s) {
  // Edge case: empty string
  if (s.length === 0) return true;

  // Initialize stack
  const stack = [];
  
  // Map for matching brackets
  const map = {
    '(': ')',
    '{': '}',
    '[': ']'
  };

  // Traverse the string
  for (let char of s) {
    // If character is an opening bracket, push to stack
    if (map[char]) {
      stack.push(char);
    } else {
      // If character is a closing bracket, check stack
      const topElement = stack.pop();
      if (map[topElement] !== char) {
        return false;
      }
    }
  }

  // Check if stack is empty
  return stack.length === 0;
}

// Test cases
console.log(isValid("()")); // true
console.log(isValid("()[]{}")); // true
console.log(isValid("(]")); // false
console.log(isValid("([)]")); // false
console.log(isValid("{[]}")); // true