Solving Leetcode 20: Valid Parentheses in JavaScript

The Problem:

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 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

The first thing I’m going to do is create a stack that will contain the array of values.

var isValid = function(s){
const stack = [];
}

Next, I will iterate through the string:

var isValid = function(s){
const stack = [];
for (let i = 0; i < s.length; i++) {
}
}

Now, we need to check that the character that we’re on is an open parenthesis, if it is, we’re going to push the closing parenthesis to the stack. If it isn’t, and is instead a different opening bracket, we will push that other bracket’s closing bracket to the stack.

Remember: We have three bracket types in total.

var isValid = function(s){
const stack = [];
for (let i = 0; i < s.length; i++) {
if(s.charAt(i) === '(' )
     stack.push(')' )
   else if(s.charAt(i) === '[' )
      stack.push(']' )
   else if(s.charAt(i) === '{' )
      stack.push('}'  )
   
}
}

Photo by Herr Bohn on Unsplash

If you haven’t passed out yet, keep it together, we’re half-way through.

Now, if the character at i isn’t an open bracket, we’re going to pull a character from the stack and check if the last element in the array matches it. If it doesn’t, we’re going to return “false”.

var isValid = function(s){
const stack = [];
for (let i = 0; i < s.length; i++) {
if(s.charAt(i) === '(' )
     stack.push(')' )
   else if(s.charAt(i) === '[' )
      stack.push(']' )
   else if(s.charAt(i) === '{' )
      stack.push('}'  )
   else if(stack.pop() !== s.charAt(i)) 
     return false;
   }
}

From here, we will check to see if the stack still contains characters.

If it does, that means that the parenthesis (and other brackets) are not closed. So, we return false.

If the stack is empty, that means everything matched up and we return true.

var isValid = function(s){
const stack = [];
for (let i = 0; i < s.length; i++) {
if(s.charAt(i) === '(' )
     stack.push(')' )
   else if(s.charAt(i) === '[' )
      stack.push(']' )
   else if(s.charAt(i) === '{' )
      stack.push('}'  )
   else if(stack.pop() !== s.charAt(i)) 
     return false;
   }
if(stack.length !== 0)
        return false
    else
        return true;
}

✨✨✨And that’s it!

Tish⚡️🎧🌙