Understanding and Solving Regular Expression Matching

Regular expressions, colloquially known as regex, are a foundational part of modern computing. They're a staple in string pattern matching, offering a robust way to recognise sequences of characters. LeetCode's Regular Expression Matching problem explores the mechanics of two special characters in regex: . and *.

This is considered a 'hard' coding problem, and you would be incredibly unlucky to get presented with this during an interview. Nevertheless, a little knowledge will help, so let's unravel this challenge.

Understanding the Problem

Problem Statement

Given an input string (s) and a pattern (p), implement regular expression matching with support for . and *.

• . matches any single character,
• * matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Examples

• s = "aa", p = "a". Returns false.
• s = "aa", p = "a*" Returns true.

This is a unique challenge as we are essentially being asked to replicate a basic regex engine. It can be tackled with a recursive approach, dynamic programming, or using a backtracking strategy.

Solution: Recursive Approach

A recursive solution breaks down the problem into simpler versions of itself. At every step, we can match a piece of the string against a piece of the pattern until we either have a match, or we otherwise run out of string and/or pattern.

A Solution Using TypeScript

const isMatch = (s: string, p: string): boolean => {  // Base case  if (!p.length) return !s.length;  // Check if the first characters match (or if pattern has a '.')  const firstMatch = s.length && (s[0] === p[0] || p[0] === '.');  // Check for a '*' at the second position in the pattern  if (p.length >= 2 && p[1] === '*') {    return (      // Try not using '*' (i.e., use it to represent zero occurrence)      isMatch(s, p.substring(2)) ||      // Use '*' to represent one or more occurrence      (firstMatch && isMatch(s.substring(1), p))    );  }  return firstMatch && isMatch(s.substring(1), p.substring(1));};

How It Works

1. Base Case:

   If the pattern p is empty, then the input string s should also be empty for a successful match.

2. First Character Match:

   Next, we check if the first characters of the string and pattern match. They match if they are the same or if the pattern has a ..

3. Handling

   *: If the second character in the pattern is *, we have two choices:
4. Assume * represents zero occurrences of the preceding element and match the string with the remaining pattern.
5. Assume * represents one occurrence (or more) and move to the next character in the string but use the same pattern.
6. If there is no *, we just move to the next characters in both the string and the pattern.

Walking the Solution Step‑By‑Step

Take s = "aab" and p = "c*a*b".

1. We notice that the second character in p is *, so we have two choices.
2. First, we try using it as zero occurrence, so we match s with a*b. This doesn't work since the first characters don't match.
3. Next, we consider * as one or more occurrence. Now, s becomes "aab" and p remains "cab".
4. We continue this way, using recursion, until we find a successful match or exhaust our options.

Recursive Solution vs. Dynamic Programming

A recursive solution mirrors the shape of the problem nicely: compare the current character, then decide what to do when the next pattern token is *. That makes it a good teaching version, but repeated subproblems can make it expensive.

The usual optimisation is dynamic programming or memoisation. Store whether a given string index and pattern index can match, then reuse that answer instead of recalculating the same branch again.

Edge Cases to Cover

Test empty strings, empty patterns, .*, repeated stars, literal characters after a star, and patterns that almost match but leave one character behind. These cases prove whether the implementation handles both "match zero" and "match one or more" paths correctly.

Wrapping Up

The Regular Expression Matching problem offers a sneak peek into the inner workings of regex engines. Whilst the recursive solution elucidated above provides a clear approach, it isn't the most optimal.

Dynamic programming can offer a more efficient solution by avoiding redundant computations, but it becomes much more complicated and ‑ perhaps ‑ is a tale for another time.

In essence, understanding and solving this problem equips web developers with deeper insights into string manipulations and pattern recognition.