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

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

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →