HardStringDynamic ProgrammingRecursion

Regular Expression Matching

1 approach, code in all languages

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 unlock the solution

See 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

You've got the patterns

Patterns get you through the screen. Shipping gets you hired.

FDE Coach is a cohort-based program in frontend, backend, AWS, and AI where you build real products and get referred to 200+ hiring partners. The free live workshop is the fastest way to see how we teach.

Join the free workshop Explore the program

750+ engineers trained · frontend, backend, AWS & AI