Regular Expression Matching

Q: What is the time complexity of Regular Expression Matching?

The table solution runs in O(n × m) time, where n is the length of s and m the length of p , because each cell reads at most two others. It needs O(n × m) memory for the full table, or O(m) with two rows. Plain recursion can take exponential time on patterns with many stars.

Q: Why does a star cell read the cell above and not the diagonal?

The cell above, dp[i-1][j] , is the same pattern with one letter less of s , and the star still in it. So after the star eats s[i-1] , it can eat s[i-2] too, and so on up the column. The diagonal-style cell dp[i-1][j-2] removes the star after one letter, which allows exactly one copy instead of any number.

Q: How is this different from wildcard matching?

In wildcard matching, as in file name patterns, * stands on its own and matches any run of characters, and ? matches one character. Here * only repeats the element before it, and the any-text pattern is .* . Both are solved with a table over prefixes, but the star transition differs: wildcard reads dp[i][j-1] or dp[i-1][j] .

HardDynamic programming Recursion

+10

You get a string s and a pattern p. In the pattern, a letter matches that same letter, a dot . matches any one letter, and a star * means zero or more copies of the element right before it, which is a letter or a dot. Return true if the pattern matches the whole of s, not only a part of it, and false otherwise.

Function

isMatch(s: string, p: string) → boolean

sstring: the string to match, lowercase letters only
pstring: the pattern of letters, dots and stars
Returnsboolean: true if p matches all of s, false otherwise

Constraints

1 ≤ s.length ≤ 1000
1 ≤ p.length ≤ 1000
s contains only lowercase English letters.
p contains only lowercase English letters, . and *.
Every * follows a letter or a ., so p never starts with * and never has two stars in a row.

Examples

Input: s = "moon"p = "mo*n"
Output: true
Explanation: o* takes both o letters, so m, o* and n spell moon exactly.

Input: s = "tree"p = "t.e"
Output: false
Explanation: t.e matches only three-letter strings: t, any letter, then e. It matches tre at the start of tree, but the last e is left over, and a match must cover all of s.

Input: s = "sky"p = "z*s.*y"
Output: true
Explanation: z* takes zero copies of z, s matches s, .* takes the k, and y matches y. A starred letter can stand for nothing, so a z that never appears in sky costs nothing.

+29 hidden tests on Submit

Follow-up

Can you also support +, one or more copies of the element before it, with the same table?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

A star can take any number of copies, and the right number depends on what comes after it. Taking as many as possible fails: against aaa, the pattern a*a lets a* eat all three letters and leaves nothing for the last a. The idea that cracks it is to treat a letter and its star as one unit with two moves: skip it, or let it eat one letter and stay where it is. A table records whether each prefix of s matches each prefix of p, so every choice is tried once, and two rows of it are enough.

Match from the left with recursion

Correct, but does not finish on the largest tests

Intuition

Let match(i, j) answer whether the suffix s[i:] matches the suffix p[j:]. If the pattern is used up, it matches only if the string is used up too. Otherwise compute first: there is a letter s[i], and p[j] is that letter or a dot.

Now look one character ahead. If p[j+1] is a star, p[j]* is one unit with two moves. It can take zero copies: skip both characters with match(i, j+2). Or, if first holds, it can take one copy: eat s[i] and stay on the same unit with match(i+1, j), ready to take another. Staying on j is what lets one star take any number of letters, one at a time. Without a star, p[j] must match exactly one letter: first and match(i+1, j+1).

It is slow because every star splits the search in two, and a failure is often found only at the very end. Take 30 letters a against ten copies of a* and then a b. The recursion tries every way to share some or all of the 30 a letters among the ten stars, about 8.5 × 10^8 ways, and makes about 2 × 10^9 calls before it can answer false. The large tests have 1000 letters. Yet there are only (n+1) × (m+1) different pairs (i, j).

Algorithm

Write match(i, j) for the suffixes starting at i and j.
If j is past the end of p, return whether i is past the end of s.
Set first to whether s[i] exists and p[j] is s[i] or a dot.
If p[j+1] is a star, return match(i, j+2) or first and match(i+1, j).
Otherwise return first and match(i+1, j+1). The answer is match(0, 0).

def isMatch(s, p):
    n, m = len(s), len(p)

    def match(i, j):
        # Does s[i:] match p[j:]?
        if j == m:
            return i == n
        first = i < n and p[j] in (s[i], ".")
        if j + 1 < m and p[j + 1] == "*":
            # use p[j] zero times, or let it eat s[i] and stay on the same x*
            return match(i, j + 2) or (first and match(i + 1, j))
        return first and match(i + 1, j + 1)

    return match(0, 0)

Fill a table of prefixes

Intuition

State. Let dp[i][j] say whether the first i letters of s match the first j characters of p. Index 0 stands for an empty prefix.

Base row and column. dp[0][0] is true: an empty pattern matches an empty string. Column 0 is false below it, because an empty pattern cannot match a letter. Row 0 is the subtle one: a pattern prefix matches the empty string only if every element in it is starred, like z* or a*b*. So dp[0][j] is true when p[j-1] is a star and dp[0][j-2] is true.

Transitions. If p[j-1] is a letter or a dot, it must match the last letter s[i-1], and the rest must match: dp[i-1][j-1], the diagonal. If p[j-1] is a star, its element is x = p[j-2], and the star has two moves. Zero copies: drop x* from the pattern, dp[i][j-2], two cells to the left. One more copy: if x matches s[i-1], that letter is one of the copies, and the same x* still has to finish the shorter string, so read dp[i-1][j], the cell right above, in the same column. Each copy is one step up that column, which is how a single star covers any number of letters.

Here is the table for sky and z*s.*y, with columns for the prefixes "", z, z*, z*s, z*s., z*s.*, z*s.*y (T is true, F is false). Row "" is [T, F, T, F, F, F, F]: only z* can be empty. Row s is [F, F, F, T, F, T, F]: s matches s with z* empty above it on the diagonal, and .* then takes zero copies. Row sk is [F, F, F, F, T, T, F]: the cell for z*s.* gets its true from one more copy, the dot eating k, read from the T right above it. Row sky is [F, F, F, F, F, T, T]: the dot star eats y the same way, a second step up the column, and then y matches y on the diagonal. The last cell is true.

Every cell reads the row above or cells to its left, so filling row by row, left to right, finds them ready. That is (n+1) × (m+1) cells, about 10^6 for the largest tests, with constant work each.

Algorithm

Create a table dp of (n+1) × (m+1) false values and set dp[0][0] to true.
For j from 2 to m, set dp[0][j] to true when p[j-1] is a star and dp[0][j-2] is true.
For each cell with i ≥ 1 and j ≥ 1, if p[j-1] is a star, set it to dp[i][j-2] or (p[j-2] matches s[i-1] and dp[i-1][j]).
Otherwise set it to (p[j-1] matches s[i-1]) and dp[i-1][j-1].
Return dp[n][m].

def isMatch(s, p):
    n, m = len(s), len(p)
    # dp[i][j]: do the first i letters of s match the first j characters of p?
    dp = [[False] * (m + 1) for _ in range(n + 1)]
    dp[0][0] = True  # an empty pattern matches an empty string
    for j in range(2, m + 1):
        # an empty string matches only patterns like x*y*z*
        dp[0][j] = p[j - 1] == "*" and dp[0][j - 2]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if p[j - 1] == "*":
                zero = dp[i][j - 2]  # use p[j-2] zero times
                more = p[j - 2] in (s[i - 1], ".") and dp[i - 1][j]  # one more copy eats s[i-1]
                dp[i][j] = zero or more
            else:
                dp[i][j] = p[j - 1] in (s[i - 1], ".") and dp[i - 1][j - 1]
    return dp[n][m]

Keep only two rows

Intuition

Row i reads two cells from row i-1, the diagonal and the cell above, and one cell of its own, two to the left. Rows further up are never read again. Keep two arrays: prev for the finished row and cur for the row you are filling, and swap them after each letter of s. The transitions stay the same: zero copies is cur[j-2], one more copy is prev[j], a plain match is prev[j-1].

Start with prev as the base row for the empty string. Set cur[0] to false at the start of every row: after a swap, cur holds an old row, and the base row's first entry is true.

Each row has m + 1 entries, so memory drops from about 10^6 cells to two rows of 1001. Unlike edit distance, you cannot swap the two inputs to make the rows shorter, because the string and the pattern play different roles.

Algorithm

Fill prev with the base row: true at 0, and at j when p[j-1] is a star and prev[j-2] is true.
For each letter of s, set cur[0] to false.
Fill cur[1..m]: a star cell is cur[j-2] or (the element matches and prev[j]); any other cell is (it matches) and prev[j-1].
Swap prev and cur.
Return prev[m].

def isMatch(s, p):
    n, m = len(s), len(p)
    # prev[j]: do the letters of s before the current one match the first j characters of p?
    prev = [False] * (m + 1)
    prev[0] = True  # row 0: the empty string
    for j in range(2, m + 1):
        prev[j] = p[j - 1] == "*" and prev[j - 2]  # only patterns like x*y*z* match it
    for i in range(1, n + 1):
        cur = [False] * (m + 1)  # cur[0] stays False: an empty pattern matches no letters
        for j in range(1, m + 1):
            if p[j - 1] == "*":
                zero = cur[j - 2]  # use p[j-2] zero times
                more = p[j - 2] in (s[i - 1], ".") and prev[j]  # one more copy eats s[i-1]
                cur[j] = zero or more
            else:
                cur[j] = p[j - 1] in (s[i - 1], ".") and prev[j - 1]
        prev = cur
    return prev[m]

Pitfalls and edge cases

Most wrong answers come from the star: what it repeats, how many times, and where it can match nothing.

Letting a star take as many letters as it can. a*a against aaa is a match, but a greedy a* eats all three letters and the last a fails.
Reading dp[i-1][j-2] for one more copy. That lets a star take at most one letter, so aa against a* comes out false. Stay in the star's column: dp[i-1][j].
Leaving row 0 all false except the first cell. Then b against a*b fails, because the b needs a* to match the empty prefix in front of it.
Comparing s[i-1] with the star itself instead of with its element p[j-2].
Treating * as "any text", as in file name patterns. Here it repeats only the element before it; any text is .*.
Accepting a partial match. t.e fits the start of tree, but the answer is false because a letter is left over.
Forgetting cur[0] = false in the two row version. After the first swap, cur[0] holds the true of the base row.

Frequently asked questions4

What is the time complexity of Regular Expression Matching?

The table solution runs in O(n × m) time, where n is the length of s and m the length of p, because each cell reads at most two others. It needs O(n × m) memory for the full table, or O(m) with two rows. Plain recursion can take exponential time on patterns with many stars.

Why does a star cell read the cell above and not the diagonal?

The cell above, dp[i-1][j], is the same pattern with one letter less of s, and the star still in it. So after the star eats s[i-1], it can eat s[i-2] too, and so on up the column. The diagonal-style cell dp[i-1][j-2] removes the star after one letter, which allows exactly one copy instead of any number.

How is this different from wildcard matching?

In wildcard matching, as in file name patterns, * stands on its own and matches any run of characters, and ? matches one character. Here * only repeats the element before it, and the any-text pattern is .*. Both are solved with a table over prefixes, but the star transition differs: wildcard reads dp[i][j-1] or dp[i-1][j].

Why not use the regex library of the language?

An interviewer wants the algorithm, not a library call. There is also a real risk: many regex engines match by backtracking, which is the slow recursion of the first approach. A pattern like ten copies of a* followed by b, against a long run of a letters, can make such an engine run for minutes. The table always finishes in O(n × m).

Python

def isMatch(s, p):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

s = "moon"
p = "mo*n"

Expected

true

Regular Expression Matching

Function

Constraints

Examples

Hints

Solution

Match from the left with recursion

Fill a table of prefixes

Keep only two rows

Pitfalls and edge cases

Frequently asked questions4

Similar problems