Regular Expression Matching - Video Solutions

Problem Overview: Given a string s and a pattern p, determine if the entire string matches the pattern. The pattern supports two special characters: . which matches any single character, and * which matches zero or more of the preceding element. The match must cover the whole string, not just a substring.

Approach 1: Recursive Backtracking with Memoization (Time: O(m*n), Space: O(m*n))

The natural way to reason about the problem is recursion. Compare characters from left to right and decide how the pattern behaves. When the next character in the pattern is *, you have two choices: treat it as matching zero characters (skip the pattern segment) or consume one matching character from the string and stay on the same pattern index. Without caching, this branching causes exponential work. Memoization stores results for each state (i, j) representing whether s[i:] matches p[j:]. Each state is computed once, reducing complexity to O(m*n). This approach closely mirrors the recursive definition of regex rules and is easier to reason about when first learning the problem. It combines recursion with dynamic programming to avoid repeated work.

Approach 2: Dynamic Programming Tabulation (Time: O(m*n), Space: O(m*n))

Bottom‑up dynamic programming converts the recursive states into a table. Define dp[i][j] as whether the first i characters of the string match the first j characters of the pattern. Iterate through the table while handling three cases: direct character match, wildcard ., and star *. The star is the tricky part. It can represent zero occurrences (look two positions back in the pattern) or multiple occurrences if the preceding character matches the current string character. By filling the table row by row, every state depends only on previously computed states. This iterative version avoids recursion overhead and is usually preferred in production code. The solution relies heavily on reasoning about pattern transitions in string processing.

Recommended for interviews: Start by explaining the recursive idea since it mirrors how regex rules are defined. Then introduce memoization to remove exponential recomputation. Interviewers typically expect the O(m*n) dynamic programming solution because it demonstrates understanding of state design and pattern transitions. Showing both the recursive memoized solution and the bottom‑up DP version signals strong mastery of dynamic programming problems.