LeetCode problem #10 — Regular Expression Matching (JavaScript)

In this LeetCode challenge we’re asked to implement a pattern matching function, which will take a string and a pattern, and return whether or not the two match.

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 (.).

A character (E.G. “a”) will match exactly itself only one time. For example, a string of “a” and a pattern of “a” will match, but a string of “aa” and a pattern of “a” will not.

An asterisk will match the preceding pattern character 0 or more times. For example, a string of “a” and a pattern of “a*” will match, as will a string of “aaaa” and a pattern of “a*”. In demonstration of a zero-match, a string of “ac” and a pattern of “ab*c” will also match, because “a” was matched once, “b” was matched 0 times, and “c” was matched once.

Finally, a full-stop will match any character only one time. For example, a string of “a” will match “.”, as will a string of “ab” against a pattern of “..”, but a string of “aa” will not match a pattern of “.”.

One additional complication is that asterisks can follow full-stops. This means that a string of “abc” will match “.*”, because the any-character allowing full-stop was matched 3 times.

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.

A good example of this is the string “abc” and the pattern “a.*c”. We know that “a” will match “a”, and we know that “.” will match “b”. But because “.” has a trailing asterisk, it will also match “c”, however, if it does match “c”, then the “c” in the pattern is never used, and the match fails.

How do we solve this? Well, we have to run multiple checks in parallel. We have to check both paths, as well as any other paths that occur when traversing through both paths. Two diverging paths quickly become 4, and then 8, and before you know it you have hundreds of possible routes to match the pattern against the string.

We need some code.

Solution #1: Recursion

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

This runs pretty much exactly as stated in the above complication. We traverse both the string and the pattern, branching off at every point to conduct separate checks, until a path finally succeeds. If no paths have succeeded by the time we reach the end of the string, the pattern was not a match, and we fail out.

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.