Regular Expression Matching

1. Define the problem

You are given a string s and a pattern p. Return true if the pattern matches the whole string, not merely part of it. The pattern can contain two special characters. A dot stands for any single character , and a star means zero or more copies of the character just before it . So "a*" matches an empty string, "a", "aa" and so on, while ".*" matches absolutely anything. The way to keep this straight is a grid: one row per length of the string, one column per length of the pattern, each square answering "does this much of the pattern match this much of the string?".

Constraints

1 ≤ s.length ≤ 20
1 ≤ p.length ≤ 20
s contains only lowercase English letters
p contains lowercase letters, dots and stars
Every star in p has a valid character before it

Example

Inputs = "aab", p = "c*a*b"

Outputtrue

Explanation "c*" stands for zero copies of c, "a*" stands for two copies of a, and then b matches b.

2. Know the words first

In plain terms

Pattern: A short description of a shape of text rather than exact text. Here it is ordinary characters plus the two special ones, dot and star.
Star: The * character. It always attaches to the character before it and means "zero or more of that character" — including none at all.
Prefix: The first few characters of something. "ca" is a prefix of "cat". This solution answers the question for every prefix pair before the full one.
Grid square: One true-or-false answer for one pair of prefixes: the first i characters of the string against the first j characters of the pattern.

3. Visualize the solution

Fill the grid one row at a time, string "aab" against pattern "cab"

Fill the grid one row at a time, string "aab" against pattern "c*a*b"

Statusempty row

String so far is empty: only patterns that can vanish match.

What happens in this step

row for s = ""
"" matches "" so column 0 is T
"c*" can be zero c's, so column 2 is T
"c*a*" can be zero of both, so column 4 is T

Columns 1 and 3 are F because a bare c or a bare a has to match something.

Step 1 of 5

Steps to visualize

The row on screen is one row of the grid: the 6 pattern prefixes, from 0 characters to all 5.
T means that pattern prefix matches the string prefix this row is about; F means it does not.
Each step moves down one row, adding one more letter of "aab".
A star copies the answer from two columns back (using zero copies) or from the row above (using one more copy).
A plain letter or dot copies the diagonal answer from the row above and one column back.
The box marks the squares that changed or decided the row.
The answer is the last square of the last row.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Fill the grid one row at a time, string "aab" against pattern "c*a*b"

Statusempty row

String so far is empty: only patterns that can vanish match.

What happens in this step

row for s = ""
"" matches "" so column 0 is T
"c*" can be zero c's, so column 2 is T
"c*a*" can be zero of both, so column 4 is T

Columns 1 and 3 are F because a bare c or a bare a has to match something.

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

function isMatch(s, p) {
  const rows = s.length + 1;
  const cols = p.length + 1;
  const table = [];

  for (let i = 0; i < rows; i += 1) {
    table.push(new Array(cols).fill(false));
  }
  table[0][0] = true;

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

  for (let i = 1; i < rows; i += 1) {
    for (let j = 1; j < cols; j += 1) {
      const pc = p[j - 1];

      if (pc === '*') {
        const prev = p[j - 2];
        const matches = prev === '.' || prev === s[i - 1];
        table[i][j] = table[i][j - 2] || (matches && table[i - 1][j]);
      } else if (pc === '.' || pc === s[i - 1]) {
        table[i][j] = table[i - 1][j - 1];
      }
    }
  }

  return table[rows - 1][cols - 1];
}

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

6. Test cases

Test cases

Input	Expected	Covers
`s = "aab", p = "cab"`	`true`	example from the description, with two stars
`s = "aa", p = "a"`	`false`	the pattern must cover the whole string, not just the start
`s = "aa", p = "a*"`	`true`	a star stretching to cover several characters
`s = "ab", p = ".*"`	`true`	dot and star together matching anything
`s = "ab", p = "a*b"`	`true`	a star used for exactly one copy
`s = "mississippi", p = "misisp*."`	`false`	a longer input where the pattern runs out early

Regular Expression Matching