Regular Expression Matching

Examples

Input: s = "aa", p = "a"
Output: false

The pattern only accounts for one character, but s has two.

Input: s = "aa", p = "a*"
Output: true

'a*' means zero or more a's, which covers "aa".

Input: s = "ab", p = ".*"
Output: true

'.' matches any character, and '*' lets it repeat as many times as needed.

Input: s = "aab", p = "c*a*b"
Output: true

'c' matches zero c's, 'a' matches both a's, and 'b' matches the final letter.

Constraints

• 1 <= s.length <= 20

• 1 <= p.length <= 20

• p is a valid pattern, and every '*' has a character (or '.') immediately before it

Approach

Build a table where cell (i, j) means: "does the first i characters of s match the first j tokens of p?"

Look at the j-th pattern token. If it's not followed by a *, it must match the current character of s directly (matching if it's a ., or the exact same letter) — so (i, j) is true only if (i-1, j-1) was true and that character matches.

If it is followed by a * (so the pattern token is really "x" for some `x`), there are two independent ways to satisfy it: use zero occurrences of `x` (skip both pattern characters, giving `(i, j-2)`), or, if `x` matches the current character of `s`, use one more occurrence of `x` and stay on this same "x" for the rest of s (giving (i-1, j)). Either possibility makes the cell true.

An empty pattern only matches an empty string, and patterns full of "x*" tokens can match an empty string too — so row 0 needs its own zero-occurrence pass before the rest of the table is filled in.

Solutions

Brute Force — Recursion

Walk s and p from the front. If the next pattern token is followed by a '*', branch into 'skip it entirely' versus 'consume one matching character and stay on it.' Otherwise, require a direct character match and advance both.

function isMatch(s, p) {
  function solve(i, j) {
    if (j === p.length) return i === s.length;

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

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

    return firstMatch && solve(i + 1, j + 1);
  }

  return solve(0, 0);
}

Time: O(2^(m + n)) in the worst case · Space: O(m + n) — recursion depth

Optimal — Bottom-Up 2D Table

Build a boolean table over (prefix length of s, prefix length of p). Handle row 0's zero-occurrence patterns first, then fill the rest using the direct-match rule or the star rule.

function isMatch(s, p) {
  const m = s.length;
  const n = p.length;
  const table = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(false));
  table[0][0] = true;

  // patterns like a*, a*b*, a*b*c* can match an empty string
  for (let j = 1; j <= n; j++) {
    if (p[j - 1] === '*' && j >= 2) {
      table[0][j] = table[0][j - 2];
    }
  }

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (p[j - 1] === '*') {
        table[i][j] = table[i][j - 2]; // zero occurrences of the element before '*'

        const prev = p[j - 2];
        if (prev === '.' || prev === s[i - 1]) {
          table[i][j] = table[i][j] || table[i - 1][j]; // one more occurrence, stay on this "x*"
        }
      } else if (p[j - 1] === '.' || p[j - 1] === s[i - 1]) {
        table[i][j] = table[i - 1][j - 1];
      }
    }
  }

  return table[m][n];
}

Time: O(m * n) · Space: O(m * n)