The scenario is you are given a string of parentheses and are tasked to check if they are valid.

The description from codewars: “Write a function that takes a string of parentheses, and determines if the order of the parentheses is valid. The function should return true if the string is valid, and false if it’s invalid.”

Example:

• () is true
• ) is false
• “” is true, empty strings are valid

Valid Parentheses: First Approach

So this is a fun little challenge and I’ll admit that I got this wrong the first time. My first approach, keeping with my motto of doing it logically first, involved using a stack to keep track of parentheses. so you loop over every character and if the stack is empty, you push the current value into the stack. If it’s not empty and the last value is different from the current value then you pop the last value.

At the end of the loop, you check the length of the stack. If the stack is empty then you return true, otherwise, return false.

function validParentheses(parens) {
    const result = parens.split("").reduce((stack, current) => {
        if(stack.length === 0 || stack[-1] === current){
            stack.push(current)
            return stack
        }
        stack.pop()
        return stack
    }, [])

    return result.length === 0
}
Code language: JavaScript (javascript)

Keen-eyed readers will already see the problem here. What if we have an input like "())(()"? This will return true because the center parentheses are not the same but it’s not a valid case.

The solution to that was to make sure they match during the check. So I updated the code to be

function validParenthesesTest(parens) {
    const result = parens.split("").reduce((stack, current) => {
        const isStackEmpty = stack.length === 0
        const isMatch = `${stack[stack.length-1] || ''}${current}` === '()'
        if(isStackEmpty || !isMatch){
            stack.push(current)
            return stack
        }
        stack.pop()
        return stack
    }, [])

    return result.length === 0
}
Code language: JavaScript (javascript)

This works and will pass all the tests.

But are we overthinking this?

What are we really trying to accomplish? We just want to know if all the parentheses match. After thinking about it for a few seconds it dawned on me that I didn’t need the stack, I didn’t need the reduce function, I didn’t even need to loop through all the characters and I could accomplish the task in fewer lines of code. how?

function validParenthesesTest(parens) {
    let workString = parens
    while(workString.indexOf('()') !== -1) {
        workString = workString.replace(/\(\)/g,'')
    }
    return workString === ''
}
Code language: JavaScript (javascript)

By removing all matching pairs until I had none left. I used the replace function to replace all occurrences of () with an empty string.

Sometimes you just have to take a step back and look at your problem again. It’s easy to get lost in the “brilliance” of your first approach that you overlook the simplest solution to the problem.

How would you solve this problem? Let me know on Twitter @phoexer and as always happy coding.