Back to LeetCode Series

LeetCode #10: Regular Expression Matching

Implement wildcard matching with . and * — from simple recursion to dynamic programming.

Difficulty: HardPattern: Recursion, DP (Dynamic Programming)Time: 12 min read

The Problem

Given an input string s and a pattern p, implement regular expression matching with support for:

  • .: 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"   → Match: ❌ false  (a ≠ aa)

s: "aa"  p: "a*"   → Match: ✅ true  (a* → 0 or more 'a')

s: "ab"  p: ".*"   → Match: ✅ true  (.* → match any sequence)

s: "aab"  p: "c*a*b*"   → Match: ✅ true  (c* = 0 times, a* = 2, b* = 1)

s: "mississippi"  p: "mis*is*p*."   → Match: ❌ false  (Doesn't fully match)

Simpler Implementation: Recursive Matching

Let‘s start with a recursive approach that‘s easier to understand.

How It Works

  1. If the pattern is empty, return s.length === 0
  2. Check if the first characters match (s[0] === p[0] or p[0] === '.')
  3. If p[1] === '*':
    • Either skip the x* (use 0 times)
    • Or consume one character and keep the pattern
  4. Otherwise, move both pointers forward
js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function isMatch(s, p) {
  // Base case
  if (!p) return !s;

  const firstMatch = s && (s[0] === p[0] || p[0] === '.');

  if (p.length >= 2 && p[1] === '*') {
    return (
      isMatch(s, p.slice(2)) ||           // Skip x*
      (firstMatch && isMatch(s.slice(1), p)) // Use one and retry
    );
  } else {
    return firstMatch && isMatch(s.slice(1), p.slice(1));
  }
}

⚠️ Warning: This is correct but exponential time — too slow for large inputs.

Try It: Simple Regex Matcher

Test your understanding with a basic matcher that handles . and *.

Preferred Implementation: Dynamic Programming

The recursive solution recalculates subproblems. We can memoize it — or build a DP table from the ground up.

Key Idea

Let dp[i][j] = whether s.slice(0,i) matches p.slice(0,j).

We fill the table from top-left to bottom-right using the same logic as recursion.

js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function isMatch(s, p) {
  const m = s.length;
  const n = p.length;
  const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(false));

  // Empty string matches empty pattern
  dp[0][0] = true;

  // Handle patterns like a*, a*b*, etc. matching empty string
  for (let j = 2; j <= n; j++) {
    if (p[j - 1] === '*') {
      dp[0][j] = dp[0][j - 2];
    }
  }

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (p[j - 1] === '*') {
        const noRepeat = dp[i][j - 2]; // Skip x*
        const repeat = (s[i - 1] === p[j - 2] || p[j - 2] === '.') && dp[i - 1][j];
        dp[i][j] = noRepeat || repeat;
      } else {
        dp[i][j] = dp[i - 1][j - 1] && 
                   (s[i - 1] === p[j - 1] || p[j - 1] === '.');
      }
    }
  }

  return dp[m][n];
}

✅ O(mn) time and space
✅ Optimal for interviews

📊 DP Table Visualizer

Watch how the DP table fills step-by-step.

DP Table Visualizer

Step-by-step regex matching with dynamic programming

600ms
#∅c*a*b*
∅
a
a
b
0 / 0 cells filled ▶️ Running...

🌍 Real-World Applications

Regex matching is everywhere — from search to security.

🔍 Search Engines

Google and grep use regex to find patterns in text. Your browser’s "Find" uses simplified versions.

🔐 Input Validation

Email, phone, password validation often uses regex patterns to enforce rules.

🧩 Compilers & Parsers

Tokenizing code (e.g. in JavaScript engines) uses finite automata — the same theory behind regex.

🛡️ Security: Log Analysis

Detecting malicious patterns in logs (e.g. SQL injection) uses regex-based rules.

🔑 Why This Matters: This problem teaches how to turn a recursive idea into an efficient DP solution — a skill used in AI, NLP, and compiler design.

Summary

This problem teaches how to break down complex pattern matching into recursive decisions, then optimize it with dynamic programming — a pattern used in compilers, search engines, and AI.

View All Challenges