LeetCode problem #10 — Regular Expression Matching (JavaScript)

A brief explanation

There are three basic types of pattern entry required, and they are a character (a, b, c, etc.), an asterisk (*), and a full-stop (.).

The “0 or more” complication

What makes this challenge tricky, is that a part of the pattern might match 10 times, or it might match 0 times.

Solution #1: Recursion

Big thanks to yu6 on LeetCode for their solution, which I have thoroughly commented here:

Solution #2: Cheating

I’d be remiss if I didn’t point out that you can actually just use JavaScript’s built in RegEx functionality for this challenge. But obviously, that’s not the point of this exercise:

Solution #3: Dynamic programming

It doesn’t take long reading through the comments and submissions for this problem to realise that dynamic programming is the most common solution. Now unfortunately, a dynamic programming solution is well beyond the realms of this post, but one is included in the earlier linked post (which I will link again here), so if you’re interested, please give it a look.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Duncan McArdle

Duncan McArdle

Full-stack software developer from the UK, author of the Aftermath book series, full time tech-nerd.