Clowning on LeetCode Problem #20

As part of my studies at https://flatironschool.com/, I have been exploring various LeetCode problems in both Ruby and JavaScript. As a number theory enthusiast, I actively strive to find the most elegant and computationally efficient solutions.

That said, when left-field solutions bubble out of a brainstorm, I give chase.

The problem, as stated:

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.

2. Open brackets must be closed in the correct order.

Simply put, we are parsing a string to make sure that all brackets are properly closed.

Tool #1: Stack

The problem is an easy solve via a stack. I won’t delve into the particulars, but for posterity’s sake:

Tool #99: Reg-who?

In my experience, ‘regex’ is a word that tends to elicit groans or grins from fellow developers.

Regular expressions are a programming language unto themselves, and crafting consistently performant regex is its own art. Liz Bennett said it perfectly:

Regular expressions are a delicate and precise language. They are crafted with careful deliberation into powerful forces that level text like a perfectly thrown bowling ball, knocking over all 10 pins with an instant and dazzling smash. A regular expression that is naively thrown together is like a drunkard who trips and stumbles over text, clumsily managing to roll the bowling ball down the lane, maybe hitting a pin or two.

https://www.loggly.com/blog/regexes-the-bad-better-best/

Regex isn’t a tool that I reach for often, but in an effort to avoid being that drunkard, I always lean into it when I see the opportunity.

The Trick

The “complexity” of the problem stems from the possibility of nested brackets as well as sets of brackets in series. However, an observation can be made that simplifies the problem:

A valid input string always has at least 1 pair of adjacent opening/closing brackets.

If we remove all valid, adjacent pairs and close their gaps, that same truth applies to the resulting string. We can iterate this process until we have either an empty string (success / valid), or mismatched leftovers.

Example:

1. ()[]{([])}
2. _____{()}_
3. ______{}__
4. ________

The Bowling Ball

Concise and… hilariously inefficient. Running a pattern match and creating a new string on each iteration is definitely not the path towards computational efficiency. However, solving problems from creative angles is its own sport.

Breaking down the regex pattern: /(\(\)|\[\]|\{\})/g

/ — — Open

( \(\) | \[\] | \{\} ) — — Match ‘()’ OR ‘[]’ OR ‘{}’

/g — — Close, with global modifier (find ALL matches, not just the first)

In context, s.replace(/(\(\)|\[\]|\{\})/g, ‘’) will replace any matching patterns with an empty string ‘’, thus closing the gaps. We iterate this process until there are no further matches, and return success if we are left with an empty string.

After celebrating, we promptly delete our quirky regex flex and uncomment the stack solution. 🤡