Regular Expression Matching

The problem

You are given a string s and a pattern p. Call each letter or dot of the pattern an element. A letter matches that same letter, and a dot matches any one character. A star always comes right after an element. Together they match zero or more of that letter or, after a dot, zero or more characters of any kind, which need not be equal. Return true if the pattern matches all of s, from its first character to its last, and false otherwise. s may be empty.

What to write

function solve(s: string, p: string): boolean

Input
s = "aa"
p = "a"

Output
false

Input
s = "aa"
p = "a*"

Output
true

Constraints

Stars always follow a valid element; s and p have at most 20 characters.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Both strings have at most 20 characters, so there are at most 21 × 21 = 441 pairs of a position in s and a position in p. The trouble is the star. One element with a star can take zero, one or many characters, and with several stars the combinations multiply quickly.

2. Hint 2: Ask a smaller question

   Match aab against c*a*b by hand. How many c's does c* take, and how many a's does a* take? At the moment you stood at c*, which two things could you do with it, and what was left to match after each?

3. Hint 3: Name the pattern

   At any moment only two things matter: how far you are in s and how far you are in p. Whether the rest of s matches the rest of p has one fixed answer for each such pair of positions, and many routes lead to the same pair. One answer per pair, each worked out once, is two-dimensional dynamic programming. Read the lesson on two-dimensional dynamic programming.

4. Hint 4: State the invariant

   The answer for a pair says whether the rest of s matches the rest of p. p used up: true only if s is too. Next element starred: true if skipping it works, or if the next letter fits and the same element matches from the letter after. No star: the letter must fit and the rest must match.

5. Hint 5: Sketch the pseudocode

   match(i, j): if stored, return it. If p ends at j: answer = s ends at i. Otherwise fits = letter i of s exists and element j is a dot or that letter. Star after element j: answer = match(i, j+2) or (fits and match(i+1, j)). No star: answer = fits and match(i+1, j+1). Store it. Start: match(0, 0).

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Memoize string and pattern offsets. For a starred element, either skip it or consume one matching character while keeping the same pattern offset.

The slow way

The tempting shortcut lets each star take as many letters as it can. It is wrong: aa is refused against a*a, because a* swallows both a's and leaves none for the last a. Trying every number of letters for every star is correct but slow, since many choices reach the same two positions: 20 a's against a*a*a*a*a*a*a*b take 2,072,069 calls. With stored answers it takes 288.

The insight

Look only at the next element of the pattern, a letter or a dot. Without a star it must fit the next letter, and both move on. With a star there is one decision: use the element zero times and skip it, or let it take one letter and keep it for more. Either way, the same question is left, further along in s or p, with one fixed answer.

Step by step

1. Answer each pair of positions in s and p once, and remember it. The answer for a pair says whether s from its position on matches p from its position on. Nothing else affects it, so it can be stored. A pair that comes up again returns its stored answer at once.
2. When p is used up, the answer is yes only if s is used up too. A match has to cover all of s. With nothing of the pattern left, nothing more can be covered, so the answer is true only when no letter of s is left either.
3. See whether the next letter of s fits the next element of p. The element fits when a letter of s is left and the element is a dot or that same letter. If s is used up, nothing fits. Both cases below need this fact.
4. Starred element: skip it, or let it take one letter and stay. A star allows zero or more. Zero times: jump over the element and its star. One more time: the letter must fit, and the element stays in place so that it can take further letters.
5. No star: the letter must fit, then both positions move on. Without a star the element stands for exactly one character. That character has to be the next letter of s, and then the rest of s must match the rest of the pattern.
6. Store the answer for this pair of positions and return it. The answer for a pair never changes, so a later question about the same pair costs one lookup instead of a new search. Storing a function's answers this way is called memoization.
7. Ask the question for the start of s and the start of p. Starting at the first position of both means nothing is matched yet: all of s against all of p. Other pairs are only worked out when this first question needs them.

The same numbered steps are the comments in each solution.

function solve(s, p) {
  // 1. Answer each pair of positions in s and p once, and remember it
  const memo = new Map();
  function match(i, j) {
    const key = i + "," + j;
    if (memo.has(key)) return memo.get(key);
    // 2. When p is used up, the answer is yes only if s is used up too
    let result;
    if (j === p.length) {
      result = i === s.length;
    } else {
      // 3. See whether the next letter of s fits the next element of p
      const first = i < s.length && (p[j] === "." || p[j] === s[i]);
      // 4. Starred element: skip it, or let it take one letter and stay
      // Reading past the end of p gives undefined, which is never a star.
      if (p[j + 1] === "*") {
        result = match(i, j + 2) || (first && match(i + 1, j));
      } else {
        // 5. No star: the letter must fit, then both positions move on
        result = first && match(i + 1, j + 1);
      }
    }
    // 6. Store the answer for this pair of positions and return it
    memo.set(key, result);
    return result;
  }
  // 7. Ask the question for the start of s and the start of p
  return match(0, 0);
}

function solve(s: string, p: string): boolean {
  // 1. Answer each pair of positions in s and p once, and remember it
  const memo = new Map<string, boolean>();
  function match(i: number, j: number): boolean {
    const key = i + "," + j;
    if (memo.has(key)) return memo.get(key)!;
    // 2. When p is used up, the answer is yes only if s is used up too
    let result: boolean;
    if (j === p.length) {
      result = i === s.length;
    } else {
      // 3. See whether the next letter of s fits the next element of p
      const first = i < s.length && (p[j] === "." || p[j] === s[i]);
      // 4. Starred element: skip it, or let it take one letter and stay
      // Reading past the end of p gives undefined, which is never a star.
      if (p[j + 1] === "*") {
        result = match(i, j + 2) || (first && match(i + 1, j));
      } else {
        // 5. No star: the letter must fit, then both positions move on
        result = first && match(i + 1, j + 1);
      }
    }
    // 6. Store the answer for this pair of positions and return it
    memo.set(key, result);
    return result;
  }
  // 7. Ask the question for the start of s and the start of p
  return match(0, 0);
}

def solve(s, p):
    # 1. Answer each pair of positions in s and p once, and remember it
    memo = {}

    def match(i, j):
        key = (i, j)
        if key in memo:
            return memo[key]
        # 2. When p is used up, the answer is yes only if s is used up too
        if j == len(p):
            result = i == len(s)
        else:
            # 3. See whether the next letter of s fits the next element of p
            first = i < len(s) and p[j] in (".", s[i])
            # 4. Starred element: skip it, or let it take one letter and stay
            # The length is checked first, because reading past the end of p fails.
            if j + 1 < len(p) and p[j + 1] == "*":
                result = match(i, j + 2) or (first and match(i + 1, j))
            else:
                # 5. No star: the letter must fit, then both positions move on
                result = first and match(i + 1, j + 1)
        # 6. Store the answer for this pair of positions and return it
        memo[key] = result
        return result

    # 7. Ask the question for the start of s and the start of p
    return match(0, 0)

Example 2, traced

Input
s = "aa"
p = "a*"

Output
true

Why it works

Each question is settled by the next element alone. With no star there is only one way to go on. With a star, any match either uses the element zero times or uses it for the next letter and then goes on with the same element, and both are tried. Every question asks about a later position in s or in p, so the chain ends.

Time and space

Time O(m n), extra space O(m n). Call the lengths of s and p m and n. There are at most (m + 1) × (n + 1) pairs of positions. Each is worked out once, with constant work besides the questions it asks: O(m n) time. The store holds one answer per pair: O(m n) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• When a starred element takes a letter, stay on that element so it can take more. Moving past the star lets it take one letter at most, and example 2 answers false: a* covers only one of the two a's.
• A starred element may be skipped even when the next letter does not fit it. If it must take at least one letter, c*a*b no longer matches aab, because there is no c for c* to take.
• End when p is used up, not when s is. With s used up, the rest of p can still match nothing, as a* does. Ending at the end of s answers false for an empty s against a*.

Pattern

Two-dimensional dynamic programming. Builds on Longest Increasing Path In a Matrix and Edit Distance.

Keep going