HardStringDynamic ProgrammingRecursion

Regular Expression Matching

1 approach, code in every language

You are given a text string and a pattern string. The pattern may contain two special characters: a dot '.' that stands for any single character, and a star '*' that lets the character immediately before it repeat zero or more times. Decide whether the pattern is able to describe the text from beginning to end.

Matching must cover the whole text, not just a prefix. A '*' is never the first symbol of the pattern and always follows an ordinary character or a dot, so every star has something it can repeat.

Example 1

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

Output: true

The star lets "a" appear twice, which reproduces "aa" exactly.

Example 2

Input: s = "abc", p = ".*d"

Output: false

".*" can consume "abc", but the trailing "d" then has nothing left to match, so the whole pattern fails.

Constraints

1 ≤ s.length ≤ 20
1 ≤ p.length ≤ 30
s contains only lowercase English letters
p contains lowercase letters, '.', and '*', where every '*' follows a valid character

Bottom-up 2D DP

Build a table where dp[i][j] answers whether the first i characters of the text match the first j characters of the pattern, filling it row by row.

Loading animation…

Intuition

Matching is naturally recursive: the answer for two prefixes depends on shorter prefixes. A star is the only tricky part, because it can either be dropped entirely (matching zero copies of the preceding character) or it can consume one more text character while the pattern position stays put. If we express both of those choices in terms of already-computed smaller subproblems, a table lets us avoid recomputing anything and read the final answer from the corner.

Algorithm walkthrough

1Create dp with (m+1) rows and (n+1) columns, all false, then set dp[0][0] = true because two empty strings match.
2Seed the first row: a pattern like a*b*c* can still match an empty text, so dp[0][j] copies dp[0][j-2] whenever p[j-1] is '*'.
3For each text index i and pattern index j, if the current pattern char is a normal letter or '.', require the characters to line up and inherit dp[i-1][j-1].
4If the current pattern char is '*', first take dp[i][j-2] (use zero copies); then, if the char before the star matches the current text char, also allow dp[i-1][j] (consume one more copy).
5Return dp[m][n], which tells whether the entire text is described by the entire pattern.

Implementation

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 2]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == '*':
                    dp[i][j] = dp[i][j - 2]
                    if p[j - 2] == '.' or p[j - 2] == s[i - 1]:
                        dp[i][j] = dp[i][j] or dp[i - 1][j]
                elif p[j - 1] == '.' or p[j - 1] == s[i - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
        return dp[m][n]

Time

O(m * n)

Space

O(m * n)

Every cell of the (m+1) x (n+1) table is filled once with constant work; the table can be reduced to two rows if space matters.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Strings

After the pattern

Now solve one you haven't seen.

Mask Matches The Whole Code is our own problem on the technique behind Regular Expression Matching: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free