Regular Expression Matching

Regular Expression Matching

What is this problem about?

The Regular Expression Matching problem asks you to implement pattern matching with '.' (matches any single character) and '*' (matches zero or more of the preceding element). Return whether the full string s matches the pattern p. This hard coding problem uses DP to handle all matching cases. The recursion, string, and dynamic programming interview pattern is the core.

Why is this asked in interviews?

Apple, Uber, Microsoft, Meta, Amazon, Google, Bloomberg, and many others ask this as a premier DP challenge. It tests the ability to model complex matching logic — including the tricky '*' zero-or-more case — as a clean DP recurrence.

Algorithmic pattern used

2D DP. dp[i][j] = whether s[0..i-1] matches p[0..j-1]. Base: dp[0][0]=True. dp[0][j]: true if pattern matches empty string (e.g., "ab"). Transitions:

• If p[j-1] == s[i-1] or p[j-1] == '.': dp[i][j] = dp[i-1][j-1].
• If p[j-1] == '*': dp[i][j] = dp[i][j-2] (use zero times) OR dp[i-1][j] if p[j-2] matches s[i-1] (use one more time).

Example explanation

s="aab", p="cab". dp table:

• p="c*": dp[0][2]=True (zero c's match empty).
• p="ca": dp[0][4]=True.
• Process s="aab" with p="cab". dp[3][5]=True. Match: true.

Common mistakes candidates make

• Not handling the base case for empty string matched by "xy" patterns.
• Wrong order: dp[i][j-2] for zero-match '*', not dp[i-1][j-2].
• Not checking that p[j-2] matches s[i-1] for the one-more-time case.
• Off-by-one in 1-indexed DP vs 0-indexed string.

Interview preparation tip

Regular Expression Matching is one of the hardest foundational DP problems. The '' case has two sub-cases: (1) use zero occurrences → dp[i][j-2]; (2) use one or more → check if preceding character matches current s[i-1], then dp[i-1][j]. Derive the recurrence on paper with small examples before coding. Practice Wildcard Matching ('?' and '') as a simpler warm-up before this problem.