How to fix issue in my "isParenthesisValid" algorithm code

March 9, 2022

I am solving an algorithm question whereby it requires me to ensure that brackets, parenthesis and braces are put in the correct order or sequence.

Here is a link to the question, https://leetcode.com/problems/valid-parentheses/

An example is shown below:

Here is my code for the solution:

const isParenthesisValid = (params) => {
    myList = []
    lastElement = myList[myList.length - 1]
    
    for (let i = 0; i < params.length; i++) {
        if (params[i] === "(" || params[i] === "[" || params[i] === "{" ) {
            myList.push(params[i])
        } else if ((params[i] === ")" && lastElement === "(") || (params[i] === "]" && lastElement === "[") || (params[i] === "}" && lastElement === "{")) {
            myList.pop()
        } else return false
    }
    
    return myList.length ? false : true
    
}

// I get false as an answer everytime whether the pattern is correct or wrong
// false

console.log(isParenthesisValid("[()]"))

But I don’t know why I get false everytime, I have compared my answer with someones else answer who did the same thing but it seems I am omitting something not so obvious.

I hope someone can point out in my code where i am getting it wrong.

>Solution :

Your lastElement retrieves the last element of the list at the start of the program – when there is no such element – so it’s always undefined. You need to retrieve the value inside the loop instead.

const isParenthesisValid = (params) => {
    myList = []
    for (let i = 0; i < params.length; i++) {
    const lastElement = myList[myList.length - 1]
        if (params[i] === "(" || params[i] === "[" || params[i] === "{" ) {
            myList.push(params[i])
        } else if ((params[i] === ")" && lastElement === "(") || (params[i] === "]" && lastElement === "[") || (params[i] === "}" && lastElement === "{")) {
            myList.pop()
        } else return false
    }
    
    return myList.length ? false : true
    
}

console.log(isParenthesisValid("[()]"))

Or, a bit more readably:

const isParenthesisValid = (input) => {
    const openDelimiters = [];
    for (const delim of input) {
        const lastElement = openDelimiters[openDelimiters.length - 1];
        if (delim === "(" || delim === "[" || delim === "{") {
            openDelimiters.push(delim)
        } else if ((delim === ")" && lastElement === "(") || (delim === "]" && lastElement === "[") || (delim === "}" && lastElement === "{")) {
            openDelimiters.pop()
        } else return false
    }
    return openDelimiters.length === 0;
}

console.log(isParenthesisValid("[()]"))

Another approach, linking each delimiter with an object:

const delims = {
    ')': '(',
    '}': '{',
    ']': '[',
};
const isParenthesisValid = (input) => {
    const openDelimiters = [];
    for (const delim of input) {
        if ('([{'.includes(delim)) {
            openDelimiters.push(delim)
        } else if (')]}'.includes(delim) && openDelimiters[openDelimiters.length - 1] === delims[delim]) {
            openDelimiters.pop()
        } else return false
    }
    return openDelimiters.length === 0;
}

console.log(isParenthesisValid("[()]"))