Skip to main content

10. Regular Expression Matching

hard

Match a string against a pattern with '.' (any single char) and 'x*' (zero or more of preceding char). The 'x*' rule pairs a char with the star — your DP recurrence must consume two pattern chars at a time when it sees the star.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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).

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.

Examples

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 (.)".

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

dp[i][j] = does the first i chars of s match the first j chars of p?

Hint 2

If p[j-1] is a letter or '.': dp[i][j] = dp[i-1][j-1] AND (p[j-1] == '.' OR p[j-1] == s[i-1]).

Hint 3

If p[j-1] == '*': consume 'x*' as zero copies (dp[i][j-2]) OR consume one more char from s and stay on the star (dp[i-1][j] AND (p[j-2] == '.' OR p[j-2] == s[i-1])).

Hint 4

Base: dp[0][0] = true. dp[0][j] is true when p[j-1] == '*' and dp[0][j-2] is true (the star erases its preceding char).

Solution approach

Reveal approach

Bottom-up DP over a 2D boolean table dp[m+1][n+1] with m = len(s), n = len(p). dp[i][j] is true iff the first i chars of s match the first j chars of p. Base case: dp[0][0] = true. Initialize dp[0][j] for j >= 2 by setting it true if p[j-1] == '*' AND dp[0][j-2] (the star removes its preceding char from the pattern). For each (i, j): if p[j-1] matches s[i-1] (literal match or '.'), dp[i][j] = dp[i-1][j-1]. If p[j-1] == '*', dp[i][j] = dp[i][j-2] (zero copies of preceding char) OR (dp[i-1][j] AND (p[j-2] == '.' OR p[j-2] == s[i-1])) (one more copy). Else dp[i][j] = false. Return dp[m][n]. Memoized recursion is an equally common framing — same transitions, top-down.

Complexity

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

Related patterns

  • dynamic-programming
  • string-dp
  • two-strings-table

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Meta
  • Google
  • Microsoft
  • Bloomberg

More 2D Dynamic Programming practice problems

See all 2D Dynamic Programming problems →