Regular Expression Matching Explained: Dynamic Programming, Memoization and TypeScript

Regular Expression Matching is a classic string and dynamic-programming problem.

In the standard algorithmic version, a pattern contains normal characters plus two special operators:

.  → matches any single character
*  → matches zero or more occurrences of the previous element

For example:

String:  aa
Pattern: a*

matches because a* can represent two a characters.

---

This is not a complete regex engine

Production regular-expression engines support many additional features such as:

+
?
[]
()
^
$
{n,m}

and various lookaround constructs.

The classical algorithm problem intentionally focuses only on . and * so that the matching logic can be studied clearly.

---

Dot

. matches exactly one arbitrary character.

For example:

c.t

matches:

cat
cut
cot
c9t

but does not match ct because the dot still requires one character.

---

Star

* applies to the preceding pattern element and means zero or more occurrences.

Therefore:

a*

can match:

""
a
aa
aaa

The possibility of consuming different numbers of characters is what makes the problem interesting.

---

Examples

s = "aa"
p = "a"
→ false

s = "aa"
p = "a*"
→ true

s = "ab"
p = ".*"
→ true

s = "aab"
p = "c*a*b"
→ true

In the final example, c* consumes zero characters, a* consumes two, and the final b matches directly.

---

Why dynamic programming?

Without *, matching can be performed almost directly from left to right.

With *, the algorithm must consider different possibilities:

Use previous element 0 times
Use it 1 time
Use it 2 times
...

These branches repeatedly reach the same subproblems, making Dynamic Programming or Memoization natural solutions.

---

DP state

Define:

dp[i][j]

as:

Whether the first i characters of string s completely match the first j characters of pattern p.

The final answer is therefore:

dp[s.length][p.length]

---

Base case

Two empty prefixes match:

dp[0][0] = true

A non-empty string cannot match an empty pattern.

However, an empty string can match patterns such as:

a*
a*b*
a*b*c*

because every starred element can appear zero times.

For such cases:

dp[0][j] = dp[0][j - 2]

when p[j - 1] === '*'.

---

Normal character or dot

When the current pattern character is not *, the current characters are compatible when:

s[i - 1] === p[j - 1]

or:

p[j - 1] === '.'

Then:

dp[i][j] = dp[i - 1][j - 1]

---

Handling star

When:

p[j - 1] === '*'

there are two important cases.

Zero occurrences

Ignore the previous pattern element and *:

dp[i][j] = dp[i][j - 2]

One or more occurrences

If the previous pattern element matches the current string character:

p[j - 2] === s[i - 1]

or:

p[j - 2] === '.'

then the star can consume the current character:

dp[i][j] = dp[i][j] || dp[i - 1][j]

Notice that j does not move because the same starred element may consume additional characters.

---

TypeScript implementation

function isRegexMatch(
  s: string,
  p: string
): boolean {
  const rows = s.length + 1;
  const cols = p.length + 1;

  const dp: boolean[][] = Array.from(
    { length: rows },
    () => new Array(cols).fill(false)
  );

  dp[0][0] = true;

  for (let j = 2; j <= p.length; j++) {
    if (p[j - 1] === '*') {
      dp[0][j] = dp[0][j - 2];
    }
  }

  for (let i = 1; i <= s.length; i++) {
    for (let j = 1; j <= p.length; j++) {
      const pc = p[j - 1];
      const sc = s[i - 1];

      if (pc === '.' || pc === sc) {
        dp[i][j] = dp[i - 1][j - 1];
      } else if (pc === '*') {
        dp[i][j] = dp[i][j - 2];

        const previous = p[j - 2];

        if (previous === '.' || previous === sc) {
          dp[i][j] =
            dp[i][j] || dp[i - 1][j];
        }
      }
    }
  }

  return dp[s.length][p.length];
}

Examples:

isRegexMatch("aa", "a*");
// true

isRegexMatch("ab", ".*");
// true

isRegexMatch("aab", "c*a*b");
// true

---

Complexity

For string length n and pattern length m:

Time Complexity:  O(n × m)
Space Complexity: O(n × m)

because each pair of string and pattern prefixes becomes one DP state.

Memory can be optimized in more advanced implementations, but the full matrix is usually easier to reason about and explain.

---

Recursive interpretation

A recursive solution expresses the logic naturally.

First determine whether the current characters match.

If the next pattern character is *, we have two choices:

Skip x*

or:

Consume one matching character and keep x*

Conceptually:

match(s, p):
    firstMatch = ...

    if p[1] == '*':
        return match(s, p[2:])
            OR
            (firstMatch AND match(s[1:], p))

    return firstMatch AND match(s[1:], p[1:])

Without Memoization, this can repeat many subproblems and become extremely expensive.

---

Top-down memoization

function isRegexMatchMemo(
  s: string,
  p: string
): boolean {
  const memo = new Map<string, boolean>();

  function dfs(i: number, j: number): boolean {
    const key = `${i}:${j}`;

    if (memo.has(key)) {
      return memo.get(key)!;
    }

    if (j === p.length) {
      return i === s.length;
    }

    const firstMatch =
      i < s.length &&
      (p[j] === '.' || p[j] === s[i]);

    let result: boolean;

    if (
      j + 1 < p.length &&
      p[j + 1] === '*'
    ) {
      result =
        dfs(i, j + 2) ||
        (firstMatch && dfs(i + 1, j));
    } else {
      result =
        firstMatch && dfs(i + 1, j + 1);
    }

    memo.set(key, result);
    return result;
  }

  return dfs(0, 0);
}

This approach exposes the two branches of * particularly clearly.

---

Why does the star keep the pattern index?

Consider:

a*

After consuming one a, the star may need to consume another.

Therefore the recursive branch moves the string index forward while keeping the pattern index at the same starred element.

This models unlimited repetition.

---

Regex matching vs. wildcard matching

The two problems are often confused.

In this regex problem:

. → any one character
* → repeat previous element

In common wildcard matching:

? → any one character
* → any sequence of characters

So * has fundamentally different semantics.

---

Why is .* powerful?

. represents any one character and * allows zero or more repetitions.

Therefore:

.*

can represent an arbitrary sequence of characters, including an empty one.

---

Full match vs. substring search

This algorithm asks whether the pattern matches the entire string.

For:

s = "hello"
p = "ell"

the answer is false, even though ell appears inside hello.

That distinction is important when interpreting the problem.

---

Real-world regular expressions

In application code, developers should normally use the regex engine provided by the language or runtime.

For example:

const regex = /^a.*b$/;
regex.test("axxxb");

The purpose of this algorithm is not to replace JavaScript's regex implementation. It teaches how branching pattern rules can be modeled as reusable states.

---

Validation and filtering

Regular expressions are commonly involved in:

• Input validation
• Search tools
• Log filtering
• Text processing
• Code editors
• Data extraction

However, validation often requires business rules beyond simple regex matching.

---

Regex performance and security

Some real backtracking regex engines can experience extreme runtime on carefully constructed patterns and inputs.

This class of issue is commonly associated with Regular Expression Denial of Service, or ReDoS.

The dynamic-programming algorithm described here is not a full backtracking regex engine, but the topic demonstrates why complexity matters when regular expressions are used on untrusted input.

---

Connection to automata

Regular expressions are closely related to formal languages and finite automata.

Regex patterns can conceptually be represented using structures such as:

• NFA
• DFA

Production engines may use automata, backtracking virtual machines, or hybrid approaches depending on their design.

---

Common interview question

A classic problem states:

Given strings s and p, where p contains normal characters, . and *, determine whether p matches all of s.

A good explanation should cover:

1. Dot matches one arbitrary character.
2. Star applies to the preceding element.
3. dp[i][j] represents prefix matching.
4. Star supports zero occurrences or additional consumption.
5. Empty-string initialization must handle x* groups.
6. Complexity is O(n × m).

---

Common mistakes

Treating star independently

* belongs to the preceding element.

a*

means repeated a, not arbitrary characters.

Treating star as zero-or-one

Star means zero or more, not zero or one.

Ignoring empty-string cases

"" vs "a*b*c*"

must return true.

Returning partial matches

The pattern must cover the entire input for this problem.

---

Edge cases

s = ""
p = ""
→ true

s = ""
p = "a*"
→ true

s = "a"
p = "."
→ true

s = "abc"
p = ".*"
→ true

s = "abc"
p = "abcd*"
→ true

The final example succeeds because d* can match zero d characters.

---

Conclusion

Regular Expression Matching with . and * is a compact but powerful Dynamic Programming problem.

Its key semantics are:

.  → any single character
x* → zero or more occurrences of x

For a starred element, the algorithm considers:

Zero occurrences
→ dp[i][j - 2]

or, when the preceding element matches:

Consume another character
→ dp[i - 1][j]

The standard DP solution runs in:

Time:  O(n × m)
Space: O(n × m)

More broadly, this problem is an excellent example of turning branching recursive behavior into a finite set of reusable Dynamic Programming states.