LeetCode problem #20–Valid parentheses (JavaScript)

In this LeetCode challenge, we’re asked to test whether a given string contains only valid sets of parentheses. The type of parenthesis can be braces (“{ }”), square-brackets (“[ ]”) and round-brackets (“( )”).

For the record, I think they should probably have named the question differently, as I’d normally call round-brackets parentheses, but that’s just personal preference. However for the rest of the article, I will use brackets as the general term.

Brackets are considered valid if they open and are then subsequently closed in the correct order. In others words, ([]) is valid, whereas ([)] is not.

Solution #1: If statements

In this solution we loop through the string, and for each bracket-opening, we add its corresponding close-bracket to an array of expected brackets. When we encounter these closing brackets later in the string, if they are top of the array, we remove them, and if they are not, we fail out. Once done, if the array is empty, we know that all opened brackets have been correctly closed, and so the string passes.

Solution #1A: Switch

This is effectively the same solution, but with a switch statement instead of if statements. It is slightly faster due to LeetCode optimisations for switch statements, but the difference is negligible.

Solution #2: While loop with replace

This solution is based on a brilliant post by LeetCode user wuyi365, and while it’s slower than the above, it’s also smaller, easier to read, and frankly pretty clever.

The way it works is that a while loop is created, which runs for as long as there are immediately open and closing bracket pairs (E.G. (), {} or [] ) in the string. Each time this loop runs, it removes all such occurrences.

The reason this works is that whilst valid bracket pairs remain, the string still requires processing, and once all valid bracket pairs are gone, the string is either valid (if empty) or invalid (if not empty).