How do you approach Regular Expression Matching?

Use dynamic programming where dp[i][j] means s[0..i-1] matches p[0..j-1].

What is the time complexity of Regular Expression Matching?

Time complexity: O(m n). Space complexity: O(m n).

What are common mistakes on Regular Expression Matching?

Iterating the dimensions in an order that reads a cell before it has been written. Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input. Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

gitGood.dev

← Back to problems

Regular Expression Matching

HardAlgorithms

Description

Given an input string `s` and a pattern `p`, implement regular expression matching with support for `'.'` and `'*'` where: - `'.'` Matches any single character. - `'*'` Matches zero or more of the preceding element. The matching should cover the **entire** input string (not partial).

Example 1

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

Output: false

Explanation: "a" does not match the entire string "aa".

Example 2

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

Output: true

Explanation: "*" means zero or more of the preceding element, "a". Therefore, by repeating "a" once, it becomes "aa".

Example 3

Input: s = "ab", p = ".*"

Output: true

Explanation: ".*" means "zero or more (*) of any character (.)".

Constraints

- 1 <= s.length <= 20 - 1 <= p.length <= 20 - s contains only lowercase English letters. - p contains only lowercase English letters, '.', and '*'. - It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.

Regular Expression Matching: approach, complexity and pitfalls

A hard dynamic programming problem, graded against 6 test cases (3 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

More Dynamic Programmingproblems →

If you are stuck

Show the 3-step hint ladder

Use dynamic programming where dp[i][j] means s[0..i-1] matches p[0..j-1].
Handle '*' by considering zero occurrences or one+ occurrences.
'.' matches any single character.

The optimal approach

Show the approach: Dynamic Programming

dp[i][j] = true if s[0..i-1] matches p[0..j-1]

- If p[j-1] == '.' or p[j-1] == s[i-1]: dp[i][j] = dp[i-1][j-1]

- If p[j-1] == '*': either 0 occurrences (dp[i][j-2]) or 1+ (dp[i-1][j] if p[j-2] matches s[i-1])

Time: O(m * n)
Space: O(m * n)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

← Back to problems

Regular Expression Matching

HardAlgorithms

Description

Example 1

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

Output: false

Explanation: "a" does not match the entire string "aa".

Example 2

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

Output: true

Explanation: "*" means zero or more of the preceding element, "a". Therefore, by repeating "a" once, it becomes "aa".

Example 3

Input: s = "ab", p = ".*"

Output: true

Explanation: ".*" means "zero or more (*) of any character (.)".

Constraints

Regular Expression Matching: approach, complexity and pitfalls

A hard dynamic programming problem, graded against 6 test cases (3 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

More Dynamic Programmingproblems →

If you are stuck

Show the 3-step hint ladder

Use dynamic programming where dp[i][j] means s[0..i-1] matches p[0..j-1].
Handle '*' by considering zero occurrences or one+ occurrences.
'.' matches any single character.

The optimal approach

Show the approach: Dynamic Programming

dp[i][j] = true if s[0..i-1] matches p[0..j-1]

- If p[j-1] == '.' or p[j-1] == s[i-1]: dp[i][j] = dp[i-1][j-1]

- If p[j-1] == '*': either 0 occurrences (dp[i][j-2]) or 1+ (dp[i-1][j] if p[j-2] matches s[i-1])

Time: O(m * n)
Space: O(m * n)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.