Leetcode Problem Question

• https://leetcode.com/problems/valid-parentheses/

Updated On: Sept 15, 2023

Main things to note

• Object We're using Object to save the opening and closing of the parentheses

• Stack As you know stack works in a LIFO (Last In First Out) manner. So, you can get the last parenthesis you added and then match it with the object value.

Javascript Solution

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
     let parenthesesMap = { ')': '(', '}': '{', ']': '[' };

  let stack = new Stack();

  //With Mapping
  for (let index = 0; index < s.length; index++) {
    const element = stack.getPopItem();

    if (Object.values(parenthesesMap).includes(s[index])) {
      stack.push(s[index]);
    }
    else if ((element === parenthesesMap[s[index]])) {
      stack.pop();
    } else return false;
  }

  // if Stack has value that means some open parenthesis are there
  return (stack.isEmpty()) ? true : false;
};


const s = "()[{]"
console.log(isValid(s));

class Stack {

    constructor() {
        this.items = [];
    }

    peek(){
        this.items.shift();
    }

    push(element){
        this.items.push(element);
    }

    //Get the last digit
    pop(){
        // console.log(this.items);
        return this.items.pop();
    }

    isEmpty(){
        return (this.items.length === 0)? true:false;
    }

    printStack(){
        console.log(this.items);
    }

    getSize(){
        return this.items.length;
    }

    getPopItem(){
        return this.items[this.items.length -1];
    }
}

Leetcode Result

Another Solution

If you're looking for an alternate coding solution. Please check the below. I am also adding the description I got from ChatGPT (this looks good to read :) )

function isValid(s: string): boolean {
    if(s.length ==1) return false;

    const brackets = {
        '(':')',
        '[':']',
        '{':'}',
    }

    const vals = s.split("");
    let stackArr = [];


    for (const val of vals){

        //If stackArr val is ( )
        let stackArrLength = stackArr.length-1;
        if(val != brackets[stackArr[stackArrLength]]) {
            stackArr.push(val);
            continue;
        }

        stackArr.splice(-1); //remove last item from array;

    }

    if(stackArr.length >0) return false;

    return true;
};

Here's a step-by-step description of the code:

Input Validation:

The function begins by checking if the input string s has a length of 1. If it does, it immediately returns false. This check ensures that single characters cannot be considered valid bracket expressions.

Brackets Mapping:

The code defines an object named brackets to map the opening brackets to their corresponding closing brackets. This mapping includes ( to ), [ to ], and { to }. This mapping is crucial for later bracket matching.

String Splitting:

The input string s is split into an array of characters named vals. This array will be iterated over to process each character in the input string.

Stack Initialization:

An empty array named stackArr is created. This array will be used as a stack to keep track of the opening brackets encountered in the input string.

Bracket Matching Loop:

The code enters a loop that iterates through each character (val) in the vals array.

In summary, the code utilizes a stack data structure to keep track of opening brackets and checks if the input string contains a valid bracket expression by ensuring that all opening brackets are correctly closed in the right order. If the brackets are properly balanced and nested, the function returns true; otherwise, it returns false.