Valid Parentheses (Leetcode 20)

I’m on a quest to improve my interview skills and general knowledge of Software Engineering as a whole. What better way to do so than to do coding challenges on Leetcode!

I’ll be honest Leetcode isn’t my strong point, but that’s all the more reason to get better. Each of these will be solved using my own implementation in JavaScript, and they will include a detailed walkthrough of my process.

So join me on this journey as I work my way through Neetcode’s 150 and more!

The first problem I will be tackling is valid parentheses:

Valid Parentheses

You are given a string s consisting of the following characters: '(', ')', '{', '}', '[' and ']'.**

The input string s is valid if and only if:

Every open bracket is closed by the same type of close bracket. Open brackets are closed in the correct order.Every close bracket has a corresponding open bracket of the same type.

Return true if s is a valid string, and false otherwise.

Problem Link: https://neetcode.io/problems/validate-parentheses

My Solution

Space Complexity: O(n)

• Stack of max length n
• Hashmap

Time Complexity: O(n)

• Must iterate through n chars of string s

Pseudo-code Steps

1. Define a hashmap containing closing brackets and their opening counterparts
2. Define a stack that will hold all of our opening parentheses in the order they appear
3. Iterate through string s
   1. if the current char is an opening bracket: add it to our stack
   2. else it is a closing bracket: see if it’s corresponding opening bracket is the last element in the stack
      1. if so, else pop from stack
      2. else the corresponding opening bracket isn’t the last element in the stack, return false (invalid parentheses)
4. Return stack === 0 (boolean value)

Code

class Solution {
    /**
     * @param {string} s
     * @return {boolean}
     */
    isValid(s) {
        // define stack
        // define hashmap for brackets
        let stack = []
        const map = new Map([[")", "("], ["]", "["], ["}", "{"]])

        // iterate through s
            // if char is not in map
                // add char to stack
            // else if corresponding val is the last val in stack
                // pop top of stack
            // else (closing brace but no corresponding open brace in stack)
                // return false

        for(const char of s){
            if(!map.has(char)){
                stack.push(char)
            } else if(stack[stack.length - 1] === map.get(char) ){
                stack.pop()
            } else{
                return false
            }
        }

        // return true if stack is empty, false if not empty
        return stack.length === 0
    }
}