10. Regular Expression Matching
hardAsked at AirbnbImplement regex matching with '.' (any single char) and '*' (zero or more). Airbnb asks this to test whether you can write the 2D DP recurrence and articulate why memoization beats raw recursion.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Airbnb loops.
- Glassdoor (2026-Q1)— Airbnb senior+ onsite reports include this as a recurring DP hard.
- Blind (2025-11)— Mentioned in Airbnb L5 algorithm-track interviews.
Problem
Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where '.' matches any single character and '*' matches zero or more of the preceding element. The matching should cover the entire input string (not partial).
Constraints
1 <= s.length <= 201 <= p.length <= 20s contains only lowercase English letters.p contains only lowercase English letters, '.', or '*'.It is guaranteed for each appearance of '*' there will be a previous valid character to match.
Examples
Example 1
s = "aa", p = "a"falseExample 2
s = "aa", p = "a*"trueExample 3
s = "ab", p = ".*"trueApproaches
1. Recursive (no memo)
If next pattern char is '*', either skip 'x*' or consume one matching char. Otherwise consume one char on both sides.
- Time
- Exponential worst case
- Space
- O(s + p) recursion
function isMatchRec(s, p) {
if (p.length === 0) return s.length === 0;
const first = s.length > 0 && (p[0] === s[0] || p[0] === '.');
if (p.length >= 2 && p[1] === '*') {
return isMatchRec(s, p.slice(2)) || (first && isMatchRec(s.slice(1), p));
}
return first && isMatchRec(s.slice(1), p.slice(1));
}Tradeoff: Clean recurrence. Blows up on patterns like 'a*a*a*a*b'. Memoize.
2. Top-down DP with memo (optimal-readable)
Memoize on (i, j). Same recurrence; each state computed once.
- Time
- O(m * n)
- Space
- O(m * n)
function isMatch(s, p) {
const memo = new Map();
function dp(i, j) {
const key = i + ',' + j;
if (memo.has(key)) return memo.get(key);
let res;
if (j === p.length) {
res = i === s.length;
} else {
const first = i < s.length && (p[j] === s[i] || p[j] === '.');
if (j + 1 < p.length && p[j + 1] === '*') {
res = dp(i, j + 2) || (first && dp(i + 1, j));
} else {
res = first && dp(i + 1, j + 1);
}
}
memo.set(key, res);
return res;
}
return dp(0, 0);
}Tradeoff: Polynomial. Often easiest to write correctly under interview pressure because it mirrors the recursion.
3. Bottom-up DP table
dp[i][j] = whether s[i:] matches p[j:]. Fill from bottom-right outward.
- Time
- O(m * n)
- Space
- O(m * n)
function isMatchTable(s, p) {
const m = s.length, n = p.length;
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(false));
dp[m][n] = true;
for (let i = m; i >= 0; i--) {
for (let j = n - 1; j >= 0; j--) {
const first = i < m && (p[j] === s[i] || p[j] === '.');
if (j + 1 < n && p[j + 1] === '*') {
dp[i][j] = dp[i][j + 2] || (first && dp[i + 1][j]);
} else {
dp[i][j] = first && dp[i + 1][j + 1];
}
}
}
return dp[0][0];
}Tradeoff: Same complexity; no recursion overhead. Slightly trickier to write correctly under pressure.
Airbnb-specific tips
Airbnb wants the recurrence stated before any code. Say: 'For pattern[j], if pattern[j+1] is *, I have two choices — skip x* entirely, or consume one char if it matches. Otherwise consume one on both sides.' Then memo or table — both pass. Skipping the recurrence and writing the table is a flag.
Common mistakes
- '*' modifies the PREVIOUS char, not the next.
- Confusing this with wildcard matching (LC 44) — '*' there means any sequence, not 'zero or more of preceding'.
- Off-by-one on dp table dimensions (need m+1 and n+1 for empty-string base).
Follow-up questions
An interviewer at Airbnb may pivot to one of these next:
- Wildcard matching (LC 44) — '?' = single, '*' = sequence. Different DP recurrence.
- What if you added '+' (one or more)?
- Compile-once-match-many — build an NFA/DFA from the pattern.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why memo over plain recursion?
Patterns like 'a*a*a*' hit the same (i, j) through different paths and explode exponentially. Memo caches each state to O(1).
Top-down memo or bottom-up table — which is better?
Both score equally on correctness and complexity. Memo is usually faster to write correctly under interview pressure; table has cleaner memory access patterns.
Free learning resources
Curated free links for this problem.