Regular Expression Matching

Hard Dynamic Programming Strings Original on LeetCode

Regular Expression Matching is a hard dynamic programming problem solved with the strings pattern. The best approach, optimal (bottom-up dp table), runs in O(m · n) time and O(m · n) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (plain recursion) up.

Problem

You are given a text s and a pattern p. The pattern uses two special symbols:

  • . stands for any single character.
  • * means “zero or more copies of the element right before it”.

Return true if the pattern matches the entire text, not just a part of it, and false otherwise.

Examples

Example 1

Input
s = "abbbc", p = "ab*c"
Output
true
Why
b* absorbs the three b's, and the a and c match themselves.

Example 2

Input
s = "xy", p = ".*z"
Output
false
Why
.* can cover "xy", but the pattern still needs a final z that the text does not have.

Example 3

Input
s = "fee", p = "f.*e*"
Output
true
Why
.* matches "ee" and e* matches nothing (or .* matches "e" and e* the last e).

Constraints

  • 1 <= s.length <= 20
  • 1 <= p.length <= 20
  • s has only lowercase English letters.
  • p has only lowercase English letters, . and *.
  • Every * follows a letter or a . (never at the start, never two in a row).

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 17 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (plain recursion)O(2^(m + n)) in the worst caseO(m + n)
Better (recursion with memoization)O(m · n)O(m · n)
Optimal (bottom-up DP table)O(m · n)O(m · n)

1Brute force (plain recursion)

TimeO(2^(m + n)) in the worst caseEvery star doubles the choices, and the same (i, j) pair is solved again and again.
SpaceO(m + n)Recursion depth is at most m + n.

Define match(i, j) as whether s[i..] matches p[j..]. If the next pattern element is starred, either skip it (match(i, j + 2)) or, when the current characters agree, eat one text character and keep the star (match(i + 1, j)). Otherwise the characters must agree and both indices move forward.

  1. If j == p.length, return i == s.length.
  2. first = i < s.length and (p[j] == s[i] or p[j] == '.').
  3. If p[j + 1] == '*': return match(i, j + 2) or (first and match(i + 1, j)).
  4. Else return first and match(i + 1, j + 1).
class Solution {
    public boolean isMatch(String s, String p) {
        return match(s, p, 0, 0);
    }

    private boolean match(String s, String p, int i, int j) {
        if (j == p.length()) {
            return i == s.length();
        }
        boolean first = i < s.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');
        if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
            return match(s, p, i, j + 2) || (first && match(s, p, i + 1, j));
        }
        return first && match(s, p, i + 1, j + 1);
    }
}

2Better (recursion with memoization)

TimeO(m · n)(m + 1)(n + 1) states, each doing O(1) work besides its recursive calls.
SpaceO(m · n)The memo table plus a recursion stack of depth up to m + n.

The same recursion, but remember the answer for each (i, j) pair the first time it is computed. Each pair is then solved once.

  1. Create a memo table of size (m + 1) x (n + 1), initially unknown.
  2. In match(i, j), return the stored value if present.
  3. Otherwise compute it with the same rules as the plain recursion and store it.
class Solution {
    private Boolean[][] memo;

    public boolean isMatch(String s, String p) {
        memo = new Boolean[s.length() + 1][p.length() + 1];
        return match(s, p, 0, 0);
    }

    private boolean match(String s, String p, int i, int j) {
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        boolean ans;
        if (j == p.length()) {
            ans = i == s.length();
        } else {
            boolean first = i < s.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');
            if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
                ans = match(s, p, i, j + 2) || (first && match(s, p, i + 1, j));
            } else {
                ans = first && match(s, p, i + 1, j + 1);
            }
        }
        memo[i][j] = ans;
        return ans;
    }
}

3Optimal (bottom-up DP table)

TimeO(m · n)Each of the (m + 1)(n + 1) cells is filled once in O(1).
SpaceO(m · n)The full table; no recursion stack.

Fill dp[i][j] = whether s[i..] matches p[j..], starting from the ends of both strings. The empty pattern matches only the empty text, and every other cell uses the same two rules as the recursion, reading cells that are already filled.

  1. dp[m][n] = true; the rest of row n (pattern used up, text left) stays false.
  2. For i from m down to 0, for j from n - 1 down to 0:
  3. first = i < m and (p[j] == s[i] or p[j] == '.').
  4. If j + 1 < n and p[j + 1] == '*': dp[i][j] = dp[i][j + 2] or (first and dp[i + 1][j]).
  5. Else dp[i][j] = first and dp[i + 1][j + 1].
  6. Return dp[0][0].
class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[m][n] = true;
        for (int i = m; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                boolean first = i < m && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');
                if (j + 1 < n && p.charAt(j + 1) == '*') {
                    dp[i][j] = dp[i][j + 2] || (first && dp[i + 1][j]);
                } else {
                    dp[i][j] = first && dp[i + 1][j + 1];
                }
            }
        }
        return dp[0][0];
    }
}

Edge cases to test

  • A starred element that must match zero characters, like a* against text with no a
  • .* that could swallow the whole remaining text, but must leave some for later pattern parts
  • Pattern longer than the text because of starred parts, like s = "a", p = "bca"
  • Text left over after the pattern is used up

Hints

Hint 1

Look at the pattern one element at a time, where an element is a single character or a character followed by *.

Hint 2

For x* you have two choices: skip it entirely, or (if the current text character matches x) consume one character and stay on x*.

Hint 3

The answer only depends on the pair (position in s, position in p), so there are at most (m + 1)(n + 1) distinct subproblems.

FAQ

What is the best time complexity for Regular Expression Matching?

Optimal (bottom-up DP table) runs in O(m · n) time and O(m · n) extra space. Each of the (m + 1)(n + 1) cells is filled once in O(1).

Which pattern does Regular Expression Matching use?

It is a dynamic programming problem that uses the strings pattern. Other problems with the same pattern: Edit Distance, Longest Common Subsequence, Longest Palindromic Subsequence.

Is there a brute force solution for Regular Expression Matching?

Yes. Brute force (plain recursion) takes O(2^(m + n)) in the worst case time and O(m + n) space. Define match(i, j) as whether s[i..] matches p[j..].

Which edge cases should I test for Regular Expression Matching?

A starred element that must match zero characters, like a against text with no a; . that could swallow the whole remaining text, but must leave some for later pattern parts; Pattern longer than the text because of starred parts, like s = "a", p = "bca"; Text left over after the pattern is used up.