Problem Overview
LeetCode 10 — Regular Expression Matching — asks you to implement pattern matching with support for two special characters: . (matches any single character) and * (matches zero or more of the preceding element). The match must cover the entire string, not just a substring.
For example, s = "aab", p = "c*a*b" returns true because c* matches zero c's, a* matches two a's, and b matches b. The star operator always applies to the character immediately before it, and the pattern is guaranteed to be valid (no standalone *).
This is one of the most classic hard DP problems on LeetCode. The 2D DP formulation is clean but requires careful case analysis for the star operator. Understanding the three cases (no star, star with zero match, star with one-or-more match) is the key to solving it.
- Input: string s and pattern p
- . matches any single character
- * matches zero or more of the preceding element
- Match must cover the entire string s
- Pattern is always valid (no standalone *)
DP State and Transitions
Define dp[i][j] = true if s[0..i-1] matches p[0..j-1]. Base case: dp[0][0] = true (empty string matches empty pattern). First row: dp[0][j] can be true if p[j-1] == * and dp[0][j-2] is true (the star eliminates its preceding character).
Case 1 — no star: if p[j-1] is a letter or dot, dp[i][j] = dp[i-1][j-1] AND (s[i-1] == p[j-1] OR p[j-1] == '.' ). The current characters must match, and everything before must also match.
Case 2 — star (p[j-1] == *): two sub-cases. Zero occurrences: dp[i][j] = dp[i][j-2] (skip the star and its preceding character entirely). One or more occurrences: dp[i][j] = dp[i-1][j] AND (s[i-1] == p[j-2] OR p[j-2] == '.' ) (the preceding character matches s[i-1], and the rest of s[0..i-2] matches the same pattern including the star).
The Star Has Two Choices
For x* in the pattern: either match zero x's (skip x* entirely, check dp[i][j-2]) or match one more x (if current char matches x, check dp[i-1][j] which keeps the star available for more matches). These two choices cover all possibilities.
Step-by-Step Walkthrough
Consider s = "aab", p = "c*a*b". Build a 4x6 DP table (s has length 3, p has length 5). dp[0][0] = T. First row: dp[0][1] = F (c vs empty). dp[0][2]: p[1]=*, dp[0][0]=T → T (c* matches zero c's). dp[0][3] = F. dp[0][4]: p[3]=*, dp[0][2]=T → T (a* matches zero a's). dp[0][5] = F.
Row 1 (s[0]=a): dp[1][1]: a==c? No → F. dp[1][2]: p[1]=*, zero: dp[1][0]=F. One-more: a==c? No → F. dp[1][3]: a==a? Yes, dp[0][2]=T → T. dp[1][4]: p[3]=*, zero: dp[1][2]=F. One-more: a==a? Yes, dp[0][4]=T → T. dp[1][5]: a==b? No → F.
Row 2 (s[1]=a): dp[2][3]: a==a? Yes, dp[1][2]=F → F. dp[2][4]: p[3]=*, zero: dp[2][2]=F. One-more: a==a? Yes, dp[1][4]=T → T. Row 3 (s[2]=b): dp[3][4]: *, zero: dp[3][2]=F. One-more: b==a? No → F. dp[3][5]: b==b? Yes, dp[2][4]=T → T. Answer: dp[3][5] = true.
Implementation in Python and Java
In Python: dp = [[False]*(n+1) for _ in range(m+1)]. dp[0][0] = True. Fill first row handling stars. For i in 1..m, j in 1..n: if p[j-1] == '*', dp[i][j] = dp[i][j-2] or (matches(s[i-1], p[j-2]) and dp[i-1][j]). Else dp[i][j] = matches(s[i-1], p[j-1]) and dp[i-1][j-1]. Helper: matches(a, b) = a==b or b=='.'.
In Java: boolean[][] dp = new boolean[m+1][n+1]. Same logic with charAt(). The matches helper checks equality or dot. The star transition is identical. Return dp[m][n].
A recursive top-down with memoization is equally clean: if pattern is empty, return string is empty. If pattern has *, try zero-match (recurse with pattern[2:]) or one-match (if first chars match, recurse with string[1:]). Memoize on (i, j) indices.
Recursive vs Iterative
The recursive approach mirrors the problem's natural structure: "does the rest match?" The iterative approach fills the table bottom-up. Both are O(m*n). Interviewers accept either — choose whichever you can code more confidently.
Comparison with Wildcard Matching
Wildcard Matching (LeetCode 44) uses ? (any single char) and * (any sequence of chars including empty). The star in wildcard matching is simpler — it matches any substring. In regex matching, * modifies the preceding character.
The DP transitions differ: wildcard * gives dp[i][j] = dp[i][j-1] (star matches empty so far) OR dp[i-1][j] (star absorbs one more char). Regex * gives dp[i][j] = dp[i][j-2] OR (match and dp[i-1][j]). The j-2 vs j-1 shift reflects the "preceding element" semantics.
Both problems are O(m*n) but regex matching requires more careful case analysis. If you master regex matching, wildcard matching becomes straightforward. Practice both to see how the same DP framework handles different operator semantics.
Complexity Analysis
Time complexity is O(m * n) where m = len(s) and n = len(p). We fill each cell of the DP table exactly once with O(1) work per cell. With constraints m, n <= 20 (LeetCode) or up to 1000 (some variants), this is efficient.
Space complexity is O(m * n) for the 2D DP table. A 1D optimization is possible since each row depends only on the current and previous rows, reducing space to O(n). However, the 2D version is clearer and preferred in interviews.
The recursive approach with memoization has the same O(m * n) time and space but uses O(m + n) stack space for recursion. For very long strings, the iterative approach avoids potential stack overflow.
YeetCode Flashcard Tip
Regular Expression Matching is the ultimate string DP problem. Practice it alongside Wildcard Matching and Edit Distance on YeetCode — together they cover every 2D string DP pattern you will encounter in interviews.