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 match must cover the entire input string. We assume a valid pattern made from the problem's permitted characters: each * follows a valid atom, and consecutive stars such as a** are outside the contract.

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 > 0 && (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. With s = "aab" and p = "c*a*b", skip c* by matching the same string against a*b. Zero copies of c is allowed.
2. At a*b, skipping a* would leave b, which cannot match the first a. Consume one a instead, keeping a*b as the pattern.
3. Repeat that step for the second a. The remaining string is now b; skip a* and compare it with b.
4. The two b characters match. Both remaining strings are empty, so the base case returns true.

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 and patterns, .*, several valid starred atoms such as a*b*, literals after a star, and patterns that leave a character unmatched. Every result should be a boolean, including isMatch("", "a") === false. Consecutive stars are invalid input, not another supported matching case.

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.