#10 Regular Expression Matching
frequently reported atAirbnbByteDance / TikTokAmazonGoogleMetaMicrosoft
the problem
In plain words
Match the whole string s against a pattern p built from lowercase letters, '.' and '*'. A '.' stands for any one character. A star after a character x means zero or more copies of x (x may be '.'). Return true only if the pattern covers all of s, not just a part of it.
in s = "aa", p = "a"
out false
"a" covers only one of the two letters.
in s = "aa", p = "a*"
out true
a* repeats a twice.
in s = "ab", p = ".*"
out true
.* is any number of any characters.
- 1 ≤ s.length ≤ 20
- 1 ≤ p.length ≤ 20
- s has lowercase letters; p has lowercase letters, '.' and '*'
- Every '*' comes right after a letter or a '.'
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
pattern2D DP on two strings (LCS / edit distance)
where this runsAutomaton-based regex engines such as RE2 and Go's regexp guarantee time linear in the text by tracking every pattern position that is still alive — the same bookkeeping this table does one text letter per row.
Look at the last character of the pattern prefix. A letter or '.' must match the last letter of the text, and then the shorter prefixes decide (↖). A '' gives two choices: use "x" zero times — drop two pattern characters (←←) — or let it eat one more matching letter and stay where it is (↑).
solutions
From brute force to optimal
match(i, j): does s[i..] match p[j..]? Handle "x*" by trying zero copies and one more copy.
- j at the end → match only if i is at the end too.
- first = s[i] fits p[j].
- Next char is '*' → match(i, j + 2) || (first && match(i + 1, j)).
- Otherwise first && match(i + 1, j + 1).
Every "x" branches into skip and eat-one-more; "aaa…b" against many a's explores millions of splits.
Recursion depth up to m + n.
class Solution { public boolean isMatch(String s, String p) { return match(s, p, 0, 0); } /** Does s[i..] match p[j..]? */ private boolean match(String s, String p, int i, int j) { if (j == p.length()) return i == s.length(); boolean first = i < s.length() && (p.charAt(j) == '.' || p.charAt(j) == s.charAt(i)); if (j + 1 < p.length() && p.charAt(j + 1) == '*') { return match(s, p, i, j + 2) // use "x*" zero times: skip it || (first && match(s, p, i + 1, j)); // use it once more: eat one char, keep "x*" } return first && match(s, p, i + 1, j + 1); // plain char or '.': both move on }}Only (m + 1)(n + 1) position pairs exist — cache them in a Boolean[][] (null = unknown).
- Check the memo, compute exactly as the recursion does, store.
Each pair is solved once with O(1) work.
The memo plus O(m + n) stack.
class Solution { public boolean isMatch(String s, String p) { return match(s, p, 0, 0, new Boolean[s.length() + 1][p.length() + 1]); // null = unknown } private boolean match(String s, String p, int i, int j, Boolean[][] memo) { if (j == p.length()) return i == s.length(); if (memo[i][j] != null) return memo[i][j]; boolean first = i < s.length() && (p.charAt(j) == '.' || p.charAt(j) == s.charAt(i)); boolean result; if (j + 1 < p.length() && p.charAt(j + 1) == '*') { result = match(s, p, i, j + 2, memo) || (first && match(s, p, i + 1, j, memo)); } else { result = first && match(s, p, i + 1, j + 1, memo); } return memo[i][j] = result; }}dp[i][j] = does s[0..i) match p[0..j)? Fill row by row.
- dp[0][0] = true; row 0: dp[0][j] = dp[0][j − 2] when p[j − 1] is '*'.
- '*' cell: dp[i][j − 2] || (s[i − 1] fits p[j − 2] && dp[i − 1][j]).
- Other cell: s[i − 1] fits p[j − 1] && dp[i − 1][j − 1].
- Return dp[m][n].
(m + 1)(n + 1) cells, O(1) each — 441 cells at LeetCode's limits.
The boolean table (two rows would also work).
class Solution { public boolean isMatch(String s, String p) { int m = s.length(), n = p.length(); boolean[][] dp = new boolean[m + 1][n + 1]; // dp[i][j]: does s[0..i) match p[0..j)? dp[0][0] = true; // empty text, empty pattern for (int j = 2; j <= n; j++) { if (p.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 2]; // "a*b*" can match nothing } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { char pc = p.charAt(j - 1); if (pc == '*') { dp[i][j] = dp[i][j - 2]; // zero copies of the starred char if (same(s.charAt(i - 1), p.charAt(j - 2))) dp[i][j] |= dp[i - 1][j]; // one more copy } else { dp[i][j] = same(s.charAt(i - 1), pc) && dp[i - 1][j - 1]; } } } return dp[m][n]; } private boolean same(char c, char pc) { return pc == '.' || pc == c; }}Fill the match table
in the room
How to say it in the interview
talk track
- Define the state with prefixes: "dp[i][j] = do the first i letters of s match the first j characters of p?"
- Walk the three cases: plain letter or '.', '' used zero times, '' eating one more letter.
- Say the base cases before coding: dp[0][0] = true, and row 0 can be true for patterns like "ab".
traps
- Treating '*' as a wildcard on its own (that's LC 44). Here it always repeats the character before it.
- Leaving row 0 all false: "ab" matches the empty text.
- Answering with
s.matches(p)in an interview: it works for this syntax, but it skips the whole question — andjava.util.regexbacktracks.
what they ask next
Follow-ups
Wildcard Matching (LC 44): '?' = one character, '*' = any sequence?
Same table. For '*': dp[i][j] = dp[i][j − 1] (matches nothing) || dp[i − 1][j] (eats one more character).
Support '+' (one or more)?
"x+" is "xx*": one required copy, then the usual star rule.
before you submit
Edge cases to test
- "x" pieces can match nothing: s = "aab", p = "ca*b" → true.
- '.' needs exactly one character: "a" vs ".." → false.
- The match must cover all of s: "aa" vs "a" → false.
- Many stars and no match ("aaaa…" vs "aaa*…b"): instant for the table, very slow for plain recursion.
practise next
Similar problems
- #72Edit DistanceMediumin Dynamic Programming
- #97Interleaving StringMediumin DP Patterns
- #139Word BreakMediumin Dynamic Programming