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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Regular Expression Matching and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →