Skip to main content

10. Regular Expression Matching

hard

Match a string against a pattern with '.' (any single char) and '*' (zero or more of the previous char). Recursive matching with memoization — the classic interview problem that makes string algorithms click.

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

Two pointers i, j into s and p. Recurse on (i, j).

Hint 2

Look at the next character in p: if p[j+1] is '*', branch into (a) skip the 'x*' entirely -> (i, j+2), (b) if s[i] matches p[j], consume one char -> (i+1, j).

Hint 3

If p[j+1] is not '*', match one char and recurse (i+1, j+1).

Hint 4

Base case: j == p.length -> return i == s.length. Memoize on (i, j).

Solution approach

Reveal approach

Recursive match(i, j): if j == p.length return i == s.length. Let firstMatch = i < s.length and (p[j] == s[i] or p[j] == '.'). If j + 1 < p.length and p[j+1] == '*': return match(i, j + 2) (zero occurrences of p[j]) OR (firstMatch and match(i + 1, j)) (consume one occurrence and stay on the same '*' for more). Else: return firstMatch and match(i + 1, j + 1). Memoize on (i, j) — there are O(m * n) states. Iterative DP: build dp[i][j] = does s[i..] match p[j..], filled in reverse; same transitions. Time and space both O(m * n).

Complexity

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

Related patterns

  • recursion
  • memoization
  • dynamic-programming

Related problems

Asked at

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

  • Meta
  • Google
  • Amazon
  • Microsoft
  • Bloomberg

More Recursion practice problems

See all Recursion problems →