LESSON 502 OF 639 · DYNAMIC PROGRAMMING

Regular Expression Matching in Go

Practice O(m · n)

You get a pattern p and a string s.

Return true if the pattern matches all of s. Otherwise, return false.

The pattern holds lowercase letters, dots and stars:

A letter matches that same letter.
A dot (.) matches any one letter.
A star (*) always comes right after a letter or a dot. It repeats that letter or dot zero or more times.

So b* matches "", "b", "bb" and so on. And .* matches any string, even an empty one.

The pattern must match the whole of s. Matching only a part of it is not enough.

Example 1:

Input: s = "moon", p = "mo*n"
Output: true
Explanation: m matches the m.
o* matches the two o's.
n matches the n.

Example 2:

Input: s = "seat", p = "s.a"
Output: false
Explanation: s matches the s, the dot matches the e, and a matches the a.
The t is left over, so the whole string doesn't match.

Example 3:

Input: s = "abc", p = "x*a.*"
Output: true
Explanation: x* matches zero x's, before the a.
a matches the a.
.* matches the rest, "bc".

Constraints:

s has 0 to 1,000 letters.
p has 0 to 1,000 characters.
s holds lowercase English letters only.
p holds lowercase English letters, dots and stars.
Every star comes right after a letter or a dot.

Note:

Your solution should run in O(m · n) time. Here m and n are the lengths of s and p.

Trying each way a star could match, one after another, can take exponential time. Think of "a*a*a*a*b" against many a's: every way to share the a's among the stars gets tried.
The same question comes back again and again: does s from index i match p from index j? Store each answer in a table dp[i][j], so it is worked out only once.

Fill the table from the end. dp[m][n] is true: an empty rest matches an empty rest.
For each cell, first check if p[j] matches s[i]: the same letter, or a dot. Then look at the next character of the pattern.

When p[j + 1] is a star, the pair can match nothing: dp[i][j + 2]. Or it can match s[i] and stay for more: dp[i + 1][j], when the first letter matches.
Otherwise, p[j] must match s[i], and the rest must match too: dp[i + 1][j + 1].

The answer is dp[0][0].

The table has (m + 1) × (n + 1) cells. Each one takes a constant amount of work. That is O(m · n) time and O(m · n) space.

STEP 1 OF 11

Guided

Ctrl + Enter to check